Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Keyword
- Publication
- Publication Type
Articles 1 - 18 of 18
Full-Text Articles in Geometry and Topology
Computational Geometry Column 40, Joseph O'Rourke
Computational Geometry Column 40, Joseph O'Rourke
Computer Science: Faculty Publications
It has recently been established by Below, De Loera, and Richter-Gebert that finding a minimum size (or even just a small) triangulation of a convex polyhedron is NP-complete. Their 3SAT-reduction proof is discussed.
On Reconfiguring Tree Linkages: Trees Can Lock, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
On Reconfiguring Tree Linkages: Trees Can Lock, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
Computer Science: Faculty Publications
It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an N-link tree can have 2Ω(N) equivalence classes of configurations.
Quest For Tilings On Riemann Surfaces Of Genus Six And Seven, Robert Dirks, Maria Sloughter
Quest For Tilings On Riemann Surfaces Of Genus Six And Seven, Robert Dirks, Maria Sloughter
Mathematical Sciences Technical Reports (MSTR)
The problem of kaleidoscopically tiling a surface by congruent triangles is equivalent to finding groups generated in certain ways. In order to admit a tiling, a group must have a specific set of generators as well as an involutary automorphism, T, that acts to reverse the orientation of the tiles. The purpose of this paper is to explore group theoretic and computational methods for determining the existence of symmetry groups and tiling groups, as well as to classify the symmetry and tiling groups on hyperbolic Riemann surfaces of genus 6 and 7.
Pushpush And Push-1 Are Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Pushpush And Push-1 Are Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
We prove that two pushing-blocks puzzles are intractable in 2D. One of our constructions improves an earlier result that established intractability in 3D [OS99] for a puzzle inspired by the game PushPush. The second construction answers a question we raised in [DDO00] for a variant we call Push-1. Both puzzles consist of unit square blocks on an integer lattice; all blocks are movable. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover when a …
Computational Geometry Column 39, Joseph O'Rourke
Computational Geometry Column 39, Joseph O'Rourke
Computer Science: Faculty Publications
The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
Examples, Counterexamples, And Enumeration Results For Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke
Examples, Counterexamples, And Enumeration Results For Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke
Computer Science: Faculty Publications
We investigate how to make the surface of a convex polyhedron (a polytope) by folding up a polygon and gluing its perimeter shut, and the reverse process of cutting open a polytope and unfolding it to a polygon. We explore basic enumeration questions in both directions: Given a polygon, how many foldings are there? Given a polytope, how many unfoldings are there to simple polygons? Throughout we give special attention to convex polygons, and to regular polygons. We show that every convex polygon folds to an infinite number of distinct polytopes, but that their number of combinatorially distinct gluings is …
The Possibility Of Impossible Pyramids, Thomas Q. Sibley
The Possibility Of Impossible Pyramids, Thomas Q. Sibley
Mathematics Faculty Publications
No abstract provided.
Computational Geometry Column 38, Joseph O'Rourke
Computational Geometry Column 38, Joseph O'Rourke
Computer Science: Faculty Publications
Recent results on curve reconstruction are described.
Lengths Of Geodesics On Klein’S Quartic Curve, Ryan Derby-Talbot
Lengths Of Geodesics On Klein’S Quartic Curve, Ryan Derby-Talbot
Mathematical Sciences Technical Reports (MSTR)
A well-known and much studied Riemann surface is Klein’s quartic curve. This surface is interesting since it is the smallest complex curve with maximal symmetry. In addition to this high degree of symmetry, Klein’s quartic curve can be tiled by triangles,giving rise to a tiling group generated by reflections. Using the tiling group and the universal cover of the tiling group we are able to compile a list of the lengths of the short,simple,closed geodesics on this surface. In particular,w e are able to determine whether the geodesic loops generated by the tiling are the systoles,i.e.,the shortest closed geodesics.
Rhombic Penrose Tilings Can Be 3-Colored, Thomas Q. Sibley, Stan Wagon
Rhombic Penrose Tilings Can Be 3-Colored, Thomas Q. Sibley, Stan Wagon
Mathematics Faculty Publications
No abstract provided.
Computational Geometry Column 37, Erik D. Demaine, Joseph O'Rourke
Computational Geometry Column 37, Erik D. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
Open problems from the 15th Annual ACM Symposium on Computational Geometry.
Pushpush Is Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Pushpush Is Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
Computer Science: Faculty Publications
We prove that a particular pushing-blocks puzzle is intractable in 2D, improving an earlier result that established intractability in 3D [OS99]. The puzzle, inspired by the game *PushPush*, consists of unit square blocks on an integer lattice. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover, each block, when pushed, slides the maximal extent of its free range. We prove this version is NP-hard in 2D by reduction from SAT.
A Look At Biseparating Maps From An Algebraic Point Of View, Melvin Henriksen, Frank A. Smith
A Look At Biseparating Maps From An Algebraic Point Of View, Melvin Henriksen, Frank A. Smith
All HMC Faculty Publications and Research
In [ABN], Araujo, Beckenstein, and Narici add the capstone to a series of papers by several groups of authors by showing that if ρ is a biseparating map between two algebras of all real or complex-valued functions on realcompact spaces, then it is a continuous multiple of an isomorphism between these rings. Their proof uses relatively powerful analytic and topological techniques. In what follows, the extent to which such a result can be generalized to a wider class of algebras using algebraic techniques is investigated. We are unable, however to obtain the main result of [ABN] using these techniques.
Investigation Of The Effectiveness Of Interface Constraints In The Solution Of Hyperbolic Second-Order Differential Equations, Paul Jerome Silva
Investigation Of The Effectiveness Of Interface Constraints In The Solution Of Hyperbolic Second-Order Differential Equations, Paul Jerome Silva
Theses Digitization Project
Solutions to differential equations describing the behavior of physical quantities (e.g., displacement, temperature, electric field strength) often only have finite range of validity over a subdomain. Interest beyond the subdomain often arises. As a result, the problem of making the solution compatible across the connecting subdomain interfaces must be dealt with. Four different compatibility methods are examined here for hyperbolic (time varying) second-order differential equations. These methods are used to match two different solutions, one in each subdomain along the connecting interface. The entire domain that is examined here is a unit square in the Cartesian plane. The four compatibility …
Constructible Circles On The Unit Sphere, Blaga Slavcheva Pauley
Constructible Circles On The Unit Sphere, Blaga Slavcheva Pauley
Theses Digitization Project
In this paper we show how to give an intrinsic definition of a constructible circle on the sphere. The classical definition of constructible circle in the plane, using straight edge and compass is there by translated in ters of so called Lenart tools. The process by which we achieve our goal involves concepts from the algebra of Hermitian matrices, complex variables, and Sterographic projection. However, the discussion is entirely elementary throughout and hopefully can serve as a guide for teachers in advanced geometry.
Finite Type Link Concordance Invariants, Blake Mellor
Finite Type Link Concordance Invariants, Blake Mellor
Mathematics, Statistics and Data Science Faculty Works
This paper is a generalization of the author's previous work on link homotopy to link concordance. We show that the only real-valued finite type link concordance invariants are the linking numbers of the components.
Finite Type Link Homotopy Invariants Ii: Milnor's Invariants, Blake Mellor
Finite Type Link Homotopy Invariants Ii: Milnor's Invariants, Blake Mellor
Mathematics, Statistics and Data Science Faculty Works
We define a notion of finite type invariants for links with a fixed linking matrix. We show that Milnor's triple link homotopy invariant is a finite type invariant, of type 1, in this sense. We also generalize the approach to Milnor's higher order homotopy invariants and show that they are also, in a sense, of finite type. Finally, we compare our approach to another approach for defining finite type invariants within linking classes.
The Intersection Graph Conjecture For Loop Diagrams, Blake Mellor
The Intersection Graph Conjecture For Loop Diagrams, Blake Mellor
Mathematics, Statistics and Data Science Faculty Works
Vassiliev invariants can be studied by studying the spaces of chord diagrams associated with singular knots. To these chord diagrams are associated the intersection graphs of the chords. We extend results of Chmutov, Duzhin and Lando to show that these graphs determine the chord diagram if the graph has at most one loop. We also compute the size of the subalgebra generated by these "loop diagrams."