Open Access. Powered by Scholars. Published by Universities.®
- Institution
-
- Smith College (59)
- Loyola University Chicago (5)
- University of Nevada, Las Vegas (4)
- Dartmouth College (2)
- Northern Illinois University (2)
-
- University of New Mexico (2)
- Ursinus College (2)
- Utah State University (2)
- Bucknell University (1)
- California Polytechnic State University, San Luis Obispo (1)
- Central Washington University (1)
- Claremont Colleges (1)
- Clemson University (1)
- Colby College (1)
- Eastern Washington University (1)
- Embry-Riddle Aeronautical University (1)
- Fort Hays State University (1)
- Illinois State University (1)
- Neutrosophic Systems with Applications (1)
- Nova Southeastern University (1)
- Old Dominion University (1)
- Portland State University (1)
- Prairie View A&M University (1)
- Rollins College (1)
- Technological University Dublin (1)
- The College of Wooster (1)
- The Texas Medical Center Library (1)
- The University of Southern Mississippi (1)
- University of Louisville (1)
- University of Missouri, St. Louis (1)
- Keyword
-
- Geometry (6)
- Robotics (4)
- Topology (4)
- Computational Geometry (3)
- Computer Vision (3)
-
- Computer programming (3)
- Computer science education (3)
- Genus-zero (3)
- Machine Learning (3)
- Unfolding (3)
- Algorithms (2)
- Bifurcation (2)
- Central configuration (2)
- Cluster analysis (2)
- Computer Science (2)
- Data analysis (2)
- Department of Computer Science (2)
- Department of Mathematical Sciences (2)
- Grid unfolding (2)
- Mathematics (2)
- Orthogonal polyhedra (2)
- Polyhedron (2)
- Time series (2)
- .NET Framework (1)
- 3D scanning (1)
- 49 Calculus of variations and optimal control; optimization (1)
- 53 Differential geometry (1)
- 68 Computer science (1)
- Acceleration (1)
- Albouy (1)
- Publication Year
- Publication
-
- Computer Science: Faculty Publications (59)
- Computer Science: Faculty Publications and Other Works (5)
- UNLV Theses, Dissertations, Professional Papers, and Capstones (4)
- CURE Proceedings (2)
- Honors Theses (2)
-
- Theses and Dissertations (2)
- 2025 Symposium (1)
- All Faculty Scholarship for the College of the Sciences (1)
- All Theses (1)
- Applications and Applied Mathematics: An International Journal (AAM) (1)
- Articles (1)
- CCAC Theses and Dissertations (1)
- Computer Science ETDs (1)
- Computer Science Faculty Publications (1)
- Computer Science Faculty and Staff Publications (1)
- Computer Science Summer Fellows (1)
- Computer Science and Software Engineering (1)
- Dartmouth College Master’s Theses (1)
- Dartmouth Scholarship (1)
- Department of Mathematics: Dissertations, Theses, and Student Research (1)
- Departmental Technical Reports (CS) (1)
- Dissertations (1)
- Dissertations and Theses (Open Access) (1)
- Electrical and Computer Engineering ETDs (1)
- Electronic Theses and Dissertations (1)
- HMC Senior Theses (1)
- Honors Program Theses (1)
- International Journal of Aviation, Aeronautics, and Aerospace (1)
- Masters Theses & Specialist Projects (1)
- Mathematics Summer Fellows (1)
- Publication Type
Articles 91 - 106 of 106
Full-Text Articles in Geometry and Topology
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.
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 …
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.
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 …
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 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.
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.
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.
Shadow Casting Phenomena At Newgrange, Frank Prendergast
Shadow Casting Phenomena At Newgrange, Frank Prendergast
Articles
A digital model of the Newgrange passage tomb and surrounding ring of monoliths known as the Great Circle is used to investigate sunrise shadow casting phenomena at the monument. Diurnal variation in shadow directions and lengths are analysed for their potential use in the Bronze Age to indicate the passage of seasonal time. Computer-aided simulations are developed from a photogrammetric survey to accurately show how three of the largest monoliths, located closest to the tomb entrance and archaeologically coded GC1, GC-1 and GC-2, cast their shadows onto the vertical face of the entrance kerbstone, coded K1. The phenomena occur at …