Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Sub-Riemannian geometry (7)
- Phyllotaxis (5)
- Carnot groups (4)
- Mean curvature flow (4)
- Oldroyd-B (4)
-
- Rigidity (4)
- Unfolding (4)
- Alcohol (3)
- Education (3)
- Fibonacci (3)
- Genus-zero (3)
- Graded manifold (3)
- Grid unfolding (3)
- Lie algebroid (3)
- Matroids (3)
- Periodic framework (3)
- Subelliptic PDE (3)
- Bisexual (2)
- Category of relations (2)
- College students (2)
- Combinatorics (2)
- Complex fluids (2)
- Complex geometry (2)
- Computational geometry (2)
- Convexity (2)
- Courant algebroids (2)
- Curriculum (2)
- Data science (2)
- Dirac (2)
- Disc-stacking model (2)
- Publication Year
- Publication
- Publication Type
Articles 241 - 257 of 257
Full-Text Articles in Physical Sciences and Mathematics
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.
Computational Geometry Column 36, Joseph O'Rourke
Computational Geometry Column 36, Joseph O'Rourke
Computer Science: Faculty Publications
Two results in "computational origami" are illustrated.
Pushpush Is Np-Hard In 3d, Joseph O'Rourke, The Smith Problem Solving Group
Pushpush Is Np-Hard In 3d, Joseph O'Rourke, The Smith Problem Solving Group
Computer Science: Faculty Publications
We prove that a particular pushing-blocks puzzle is intractable in 3D. 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 3D by reduction from SAT. The corresponding problem in 2D remains open.
Zero-Parity Stabbing Information, Joseph O'Rourke, Irena Pashchenko
Zero-Parity Stabbing Information, Joseph O'Rourke, Irena Pashchenko
Computer Science: Faculty Publications
Everett et al. [EHN96, EHN97] introduced several varieties of stabbing information for the lines determined by pairs of vertices of a simple polygon P, and established their relationships to vertex visibility and other combinatorial data. In the same spirit, we define the “zero-parity (ZP) stabbing information” to be a natural weakening of their “weak stabbing information,” retaining only the distinction among {zero, odd, even > 0} in the number of polygon edges stabbed. Whereas the weak stabbing information’s relation to visibility remains an open problem, we completely settle the analogous questions for zero parity information, with three results: (1) ZP information …
Lagrangian Systems On Hyperbolic Manifolds, Philip Boyland, Christophe Golé
Lagrangian Systems On Hyperbolic Manifolds, Philip Boyland, Christophe Golé
Mathematics Sciences: Faculty Publications
This paper gives two results that show that the dynamics of a time-periodic Lagrangian system on a hyperbolic manifold are at least as complicated as the geodesic flow of a hyperbolic metric. Given a hyperbolic geodesic in the Poincaré ball, Theorem A asserts that there are minimizers of the lift of the Lagrangian system that are a bounded distance away and have a variety of approximate speeds. Theorem B gives the existence of a collection of compact invariant sets of the Euler-Lagrange flow that are semiconjugate to the geodesic flow of a hyperbolic metric. These results can be viewed as …
Computational Geometry Column 35, Joseph O'Rourke
Computational Geometry Column 35, Joseph O'Rourke
Computer Science: Faculty Publications
The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.
Locked And Unlocked Polygonal Chains In 3d, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
Locked And Unlocked Polygonal Chains In 3d, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides
Computer Science: Faculty Publications
In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement. The analogous concept for closed chains is convexification: reconfiguration to a planar convex polygon. Chains that cannot be straightened or convexified are called locked. While there are open chains in 3D that are locked, we show that if an open chain has a …
Computational Geometry Column 33, Joseph O'Rourke
Computational Geometry Column 33, Joseph O'Rourke
Computer Science: Faculty Publications
Several recent SIGGRAPH papers on surface simplification are described.
A Version Of A Theorem Of Dahlberg For The Subelliptic Dirichlet Problem, Luca Capogna, Nicola Garofalo, Duy Minh Nhieu
A Version Of A Theorem Of Dahlberg For The Subelliptic Dirichlet Problem, Luca Capogna, Nicola Garofalo, Duy Minh Nhieu
Mathematics Sciences: Faculty Publications
No abstract provided.
Computational Geometry Column 34, Pankaj K. Agarwal, Joseph O'Rourke
Computational Geometry Column 34, Pankaj K. Agarwal, Joseph O'Rourke
Computer Science: Faculty Publications
Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.
Computational Geometry Column 32, Joseph O'Rourke
Computational Geometry Column 32, Joseph O'Rourke
Computer Science: Faculty Publications
The proof of Dey's new k-set bound is illustrated.
A Note On Carnot Geodesics In Nilpotent Lie Groups, Christophe Golé, Ron Karidi
A Note On Carnot Geodesics In Nilpotent Lie Groups, Christophe Golé, Ron Karidi
Mathematics Sciences: Faculty Publications
We show that strictly abnormal geodesics arise in graded nilpotent Lie groups. We construct a group, with a left invariant bracket-generating distribution, for which some Carnot geodecics are strictly abnormal and, in fact, not normal in any subgroup. In the 2-step case we also prove that these geodesics are always smooth. Our main technique is based on the equations for the normal and abnormal curves, which we derive (for any Lie group) explicitly in terms of the structure constants. © 1995 Plenum Publishing Corporation.
Optical Hamiltonians And Symplectic Twist Maps, Christophe Golé
Optical Hamiltonians And Symplectic Twist Maps, Christophe Golé
Mathematics Sciences: Faculty Publications
This paper concentrates on optical Hamiltonian systems of T*Tn, i.e., those for which Hpp is a positive definite matrix, and their relationship with symplectic twist maps. We present theorems of decomposition by symplectic twist maps and existence of periodic orbits for these systems. The novelty of these results resides in the fact that no explicit asymptotic condition is imposed on the system.
Periodic Orbits For Hamiltonian Systems In Cotangent Bundles, Christophe Golé
Periodic Orbits For Hamiltonian Systems In Cotangent Bundles, Christophe Golé
Mathematics Sciences: Faculty Publications
We prove the existence of at least cl(Af) periodic orbits for certain time-dependent Hamiltonian systems on the cotangent bundle of an arbitrary compact manifold M. These Hamiltonians are not necessarily convex but they satisfy a certain boundary condition given by a Riemannian metric on M. We discretize the variational problem by decomposing the time-1 map into a product of "symplectic twist maps". A second theorem deals with homotopically non-trivial orbits of negative curvature.
A New Proof Of The Aubry-Mather's Theorem, Christophe Golé
A New Proof Of The Aubry-Mather's Theorem, Christophe Golé
Mathematics Sciences: Faculty Publications
No abstract provided.
Ghost Circles For Twist Maps, Christophe Golé
Ghost Circles For Twist Maps, Christophe Golé
Mathematics Sciences: Faculty Publications
Completely ordered invariant circles are found for the gradient of the energy flow in the state space, containing the critical sets corresponding to the Birkhoff orbits of all rotation number. In particular, these ghost circles contain the Aubry-Mather sets and map-invariant circles as completely critical sets when these exist. We give a criterion for a sequence of rational ghost circles to converge to a completely critical one.