Continuous Blooming of Convex Polyhedra (2009)
Demaine, Erik D., Demaine, Martin L., Hart, Vi, Iacono, John, Langerman, Stefan, O'Rourke, Joseph
We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further...
Some Properties of Yao Y4 Subgraphs (2009)
The Yao graph for k=4, Y4, is naturally partitioned into four subgraphs, one per quadrant. We show that the subgraphs for one quadrant differ from the subgraphs for two adjacent quadrants in three...
Unfolding Convex Polyhedra via Quasigeodesic Star Unfoldings (2008)
Itoh, Jin-ichi, O'Rourke, Joseph, Vîlcu, Costin
We extend the notion of a star unfolding to be based on a simple quasigeodesic loop Q rather than on a point. This gives a new general method to unfold the surface of any convex polyhedron P to a...
Aloupis, Greg, Cardinal, Jean, Collette, Sebastien, Hurtado, Ferran, Langerman, Stefan, O'Rourke, Joseph, ...
A highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of...
Morphing of Triangular Meshes in Shape Space (2008)
Wuhrer, Stefanie, Bose, Prosenjit, Shu, Chang, O'Rourke, Joseph, Brunton, Alan
We present a novel approach to morph between two isometric poses of the same non-rigid object given as triangular meshes. We model the morphs as linear interpolations in a suitable shape space...
Cauchy's Arm Lemma on a Growing Sphere (2008)
Abel, Zachary, Charlton, David, Collette, Sebastien, Demaine, Erik D., Demaine, Martin L., Langerman, Stefan, ...
We propose a variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases....
Connecting Polygonizations via Stretches and Twangs (2008)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswami, Suneeta
We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves...
Connecting Polygonizations via Stretches and Twangs (2008)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswami, Suneeta
We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves...
A Class of Convex Polyhedra with Few Edge Unfoldings (2008)
Benton, Alex, O'Rourke, Joseph
We construct a sequence of convex polyhedra on n vertices with the property that, as n -> infinity, the fraction of its edge unfoldings that avoid overlap approaches 0, and so the fraction that...
20. Connecting Polygonizations via Stretches and Twangs (2008)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswani, Suneeta
We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves...
On the Maximum Span of Fixed-Angle Chains (2007)
Benbernou, Nadia, O'Rourke, Joseph
Soss proved that it is NP-hard to find the maximum 2D span of a fixed-angle polygonal chain: the largest distance achievable between the endpoints in a planar embedding. These fixed-angle chains can...
Unfolding Polyhedral Bands (2007)
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, ...
A band is de ned as the intersection of the surface of a convex polyhedron with the space between two parallel planes, as long as this space does not contain any vertices of the polyhedron. An...
Flat-State Connectivity of Linkages under Dihedral Motions (2007)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
Band Unfoldings and Prismatoids: A Counterexample (2007)
This note shows that the hope expressed in [ADL+07]--that the new algorithm for edge-unfolding any polyhedral band without overlap might lead to an algorithm for unfolding any prismatoid without...
A New Lower Bound on Guard Placement for Wireless Localization (2007)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswami, Suneeta
The problem of wireless localization asks to place and orient stations in the plane, each of which broadcasts a unique key within a fixed angular range, so that each point in the plane can determine...
Connecting Polygonizations via Stretches and Twangs (2007)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph, Ramaswami, Suneeta
We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n^2) ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves...
Unfolding Restricted Convex Caps (2007)
This paper details an algorithm for unfolding a class of convex polyhedra, where each polyhedron in the class consists of a convex cap over a rectangular base, with several restrictions: the cap's...
Unfolding Convex Polyhedra via Quasigeodesics (2007)
Itoh, Jin-ichi, O'Rourke, Joseph, Vîlcu, Costin
We show that cutting shortest paths from every vertex of a convex polyhedron to a simple closed quasigeodesic, and cutting all but a short segment of the quasigeodesic, unfolds the surface to a...
Unfolding Orthogonal Terrains (2007)
It is shown that every orthogonal terrain, i.e., an orthogonal (right-angled) polyhedron based on a rectangle that meets every vertical line in a segment, has a grid unfolding: its surface may be...
Unfolding Manhattan Towers (2007)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph
We provide an algorithm for unfolding the surface of any orthogonal polyhedron that falls into a particular shape class we call Manhattan Towers, to a nonoverlapping planar orthogonal polygon. The...
Epsilon-Unfolding Orthogonal Polyhedra (2006)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph
An unfolding of a polyhedron is produced by cutting the surface and flattening to a single, connected, planar piece without overlap (except possibly at boundary points). It is a long unsolved problem...
Grid Vertex-Unfolding Orthogonal Polyhedra (2005)
Damian, Mirela, Flatland, Robin, O'Rourke, Joseph
An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a *net*, a connected planar piece with no overlaps. A *grid unfolding* allows additional cuts along...
Partitioning Regular Polygons into Circular Pieces II:Nonconvex Partitions (2004)
Damian, Mirela, O'Rourke, Joseph
We explore optimal circular nonconvex partitions of regular k-gons. The circularity of a polygon is measured by its aspect ratio: the ratio of the radii of the smallest circumscribing circle to the...
A 2-chain can interlock with a k-chain (2004)
Glass, Julie, Langerman, Stefan, O'Rourke, Joseph, Snoeyink, Jack, Zhong, Jianyuan K.
One of the open problems posed in [3] is: what is the minimal number k such that an open, flexible k-chain can interlock with a flexible 2-chain? In this paper, we establish the assumption behind...
Unfolding Smooth Primsatoids (2004)
Benbernou, Nadia, Cahn, Patricia, O'Rourke, Joseph
We define a notion for unfolding smooth, ruled surfaces, and prove that every smooth prismatoid (the convex hull of two smooth curves lying in parallel planes), has a nonoverlapping ``volcano...
Computational Geometry Column 45 (2004)
The algorithm of Edelsbrunner for surface reconstruction by ``wrapping'' a set of points in R^3 is described.
Two Computational Geometry Libraries: LEDA and CGAL (2004)
Kettner, Lutz, Näher, Stefan, Goodman, Jacob E., O'Rourke, Joseph
Two Computational Geometry Libraries: LEDA and {CGAL} (2004)
Kettner, Lutz, Näher, Stefan, Goodman, Jacob E., O'Rourke, Joseph
A Note on Objects Built From Bricks without Corners (2003)
Damian, Mirela, O'Rourke, Joseph
We report a small advance on a question raised by Robertson, Schweitzer, and Wagon in [RSW02]. They constructed a genus-13 polyhedron built from bricks without corners, and asked whether every...
Computational Geometry Column 44 (2003)
The open problem of whether or not every pair of equal-area polygons has a hinged dissection is discussed.
Partitioning Regular Polygons into Circular Pieces I: Convex Partitions (2003)
Damian, Mirela, O'Rourke, Joseph
We explore an instance of the question of partitioning a polygon into pieces, each of which is as ``circular'' as possible, in the sense of having an aspect ratio close to 1. The aspect ratio of a...
The Effectiveness of Mathematical Models as a Human Analog (2003)
Frisch, Georg D., O'Rourke, Joseph, D'Aulerio, Louis
This paper analyzes data on the dynamic response of the living human head and neck to -Gx impact acceleration. The Calspan '3D Computer Simulator of a Motor Vehicle Crash Victim Simulator - Light...
Open Problems from CCCG 2002 (2002)
Demaine, Erik D., O'Rourke, Joseph
A list of the problems presented on August 12, 2002 at the open-problem session of the 14th Canadian Conference on Computational Geometry held in Lethbridge, Alberta, Canada.
Computational Geometry Column 43 (2002)
The concept of pointed pseudo-triangulations is defined and a few of its applications described.
Evaluation of an Advanced Automotive Restraint System using Human Subjects. (2002)
Hendler,Edwin, O'Rourke,Joseph, Domzalski,Leon, Katzeff,Mark, Schulman,Marvin
The Department of Transportation (DOT), National Highway Traffic Safety Administration (NHTSA), sponsored a research program at the Naval Air Development Center (NAVAIRDEVCEN), utilizing its...
Partitioning Orthogonal Polygons into Fat Rectangles in Polynomial Time (2002)
Joseph O'Rourke, Geetika Tewari
We provide a polynomial-time algorithm to partition an orthogonal polygon of n vertices into isothetic rectangles so that the shortest rectangle side is maximized over all rectangles. Thus no...
On Flat-State Connectivity of Chains with Fixed Acute Angles (2002)
Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana Streinu, Godfried Toussaint
We prove that two classes of fixed-angle, open chains with acute angles are "flat-state connected." A chain is flatstate connected if it can be reconfigured between any two of its planar...
Flat-State Connectivity of Linkages under Dihedral Motions (2002)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
Nonorthogonal Polyhedra Built from Rectangles (2001)
Donoso, Melody, O'Rourke, Joseph
We prove that any polyhedron of genus zero or genus one built out of rectangular faces must be an orthogonal polyhedron, but that there are nonorthogonal polyhedra of genus seven all of whose faces...
Vertex-Unfoldings of Simplicial Manifolds (2001)
Demaine, Erik D., Eppstein, David, Erickson, Jeff, Hart, George W., O'Rourke, Joseph
We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along...
Computational Geometry Column 42 (2001)
Mitchell, Joseph S. B., O'Rourke, Joseph
A compendium of thirty previously published open problems in computational geometry is presented.
Vertex-Unfoldings of Simplicial Polyhedra (2001)
Demaine, Erik D., Eppstein, David, Erickson, Jeff, Hart, George W., O'Rourke, Joseph
We present two algorithms for unfolding the surface of any polyhedron, all of whose faces are triangles, to a nonoverlapping, connected planar layout. The surface is cut only along polyhedron edges....
Enumerating Foldings and Unfoldings between Polygons and Polytopes (2001)
Demaine, Erik D., Demaine, Martin L., Lubiw, Anna, O'Rourke, Joseph
We pose and answer several questions concerning the number of ways to fold a polygon to a polytope, and how many polytopes can be obtained from one polygon; and the analogous questions for unfolding...
Computational Geometry Column 41 (2001)
The recent result that n congruent balls in R^d have at most 4 distinct geometric permutations is described.
Computational Geometry Column 40 (2000)
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...
Computational Geometry Column 39 (2000)
The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
Demaine, Erik D., Demaine, Martin L., Lubiw, Anna, O'Rourke, Joseph
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...
PushPush and Push-1 are NP-hard in 2D (2000)
Demaine, Erik D., Demaine, Martin L., O'Rourke, Joseph
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...
On the Development of the Intersection of a Plane with a Polytope (2000)
Define a ``slice'' curve as the intersection of a plane with the surface of a polytope, i.e., a convex polyhedron in three dimensions. We prove that a slice curve develops on a plane without...
Computational Geometry Column 38 (2000)
Recent results on curve reconstruction are described.
PushPush is NP-hard in 2D (2000)
Demaine, Erik D., Demaine, Martin L., O'Rourke, Joseph
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...
On the Development of the Intersection of a Plane with a Polytope (2000)
Define a "slice" curve as the intersection of a plane with the surface of a polytope, i.e., a convex polyhedron in three dimensions. We prove that a slice curve develops on a plane without...
PushPush and Push-1 are NP-hard in 2D (2000)
Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
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...
On Reconfiguring Tree Linkages: Trees can Lock (2000)
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, ...
It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. In this paper we propose a related question: whether a...
PushPush is NP-hard in 2D (2000)
Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke
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...
Computational Geometry Column 38 (2000)
Recent results on curve reconstruction are described. Reconstruction of a curve from sample points ("connect-the-dots") is an important problem studied now for twenty years. Early efforts,...
Erik Demaine, Martin Demaine, Anna Lubiw, Joseph O'Rourke
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...
PushPush and Push-1 are NP-hard in 2D (2000)
Erik L. Demaine, Joseph O'Rourke, Martin L. Demaine
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...
Open Problems from CCCG 2001 (2000)
Erik D. Demaine, Joseph O'Rourke, Ileana Streinu, John Iacono
USA. orourke@cs.smith.edu. Supported by NSF Distinguished Teaching Scholars award DUE-0123154. Figure 1: An example of a monotone matching. [Str94] Ileana Streinu. Positive and negative results on...
PushPush is NP-hard in 3D (1999)
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...
On Reconfiguring Tree Linkages: Trees can Lock (1999)
Biedl, Therese, Demaine, Erik, Demaine, Martin, Lazard, Sylvain, Lubiw, Anna, O'Rourke, Joseph, ...
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....
Computational Geometry Column 37 (1999)
Demaine, Erik D., O'Rourke, Joseph
Open problems from the 15th Annual ACM Symposium on Computational Geometry.
Polygonal Chains Cannot Lock in 4D (1999)
Cocan, Roxana, O'Rourke, Joseph
We prove that, in all dimensions d>=4, every simple open polygonal chain and every tree may be straightened, and every simple closed polygonal chain may be convexified. These reconfigurations can be...
Computational Geometry Column 36 (1999)
Two results in "computational origami" are illustrated.
Zero-Parity Stabbing Information (1999)
O'Rourke, Joseph, Pashchenko, Irena
Everett et al. 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...
Computational Geometry Column 35 (1999)
The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.
Metamorphosis of the Cube (1999)
Erik Demaine, Martin Demaine, Anna Lubiw, Joseph O'Rourke, Irena Pashchenko
Introduction The foldings and unfoldings shown in this video illustrate two problems: (1) cut open and unfold a convex polyhedron to a simple planar polygon; and (2) fold and glue a simple planar...
Polygonal Chains Cannot Lock in 4D (1999)
We prove that, for all dimensions d 4, every simple open polygonal chain may be straightened, and every simple closed polygonal chain may be convexified. Both can be achieved by algorithms that use...
PushPush is NP-hard in 3D (1999)
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...
Computational Geometry Column 33 (1998)
Several recent SIGGRAPH papers on surface simplification are described.
Computational Geometry Column 32 (1998)
The proof of Dey's new k-set bound is illustrated.
Computational Geometry Column 34 (1998)
Agarwal, Pankaj K., O'Rourke, Joseph
Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.
Computational Geometry Column 33 (1998)
Several recent SIGGRAPH papers on surface simplification are described. Keywords: Mesh simplification, decimation. The stringent demands of real-time graphics have engendered a need for...
Open Problems in the Combinatorics of Visibility and Illumination (1998)
. Joseph O'Rourke http://cs.smith.edu/ orourke/ n= n x y xy xy xy fl fln c c n g x gx y gy e x y e xy see visible illuminates vertex guard edge guard Contemporary Mathematics 1 c 0000 (copyright...
Unfolding Some Classes of Orthogonal Polyhedra (1998)
Therese Biedl, Erik Demaine, Martin Demaine, Anna Lubiw, Mark Overmars, Joseph O'Rourke, ...
In this paper, we study unfoldings of orthogonal polyhedra. More precisely, we define two special classes of orthogonal polyhedra, orthostacks and orthotubes, and show how to generate unfoldings by...
When Can a Polygon Fold to a Polytope? (1996)
We show that the decision question posed in the title can be answered with an algorithm of time and space complexity O(n 2 ), for a polygon of n vertices. We use a theorem of Aleksandrov that says...
Visibility in Pseudo-Polygons and Vertex-Edge Pseudo-Visibility Graphs (1995)
Joseph O'Rourke, Ileana Streinu
We extend the notion of visibility graph to pseudo-polygons defined on generalized configurations of points (cf. Goodman and Pollack[4]). This abstracts the classic concept by removing the condition...
Agnosticism About the Arbitrary Realization Argument (1994)
Brown, Marina, O'Rourke, Joseph
We argue that Bringsjord (1992, 1994) should be agnostic about his version (ARA1) of Block's Arbitrary Realization Argument, because Bringsjord admits to agnosticism about low-level functionalism and...
Computational Geometry Column 39 (1993)
The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane. A polygonal chain is a connected series of line segments. Chains may be open, or closed to form a...
Star Unfolding of a Polytope with Applications (1993)
Pankaj K. Agarwal, Pankaj K. Agarwal, Joseph O'Rourke, Boris Aronov, Boris Aronov, Catherine A. Schevon, ...
We define the notion of a star unfolding of the surface P of a convex polytope with n vertices, and use it to solve several problems related to shortest paths on P. The first algorithm computes the...
Computational Geometry Column 31 (1993)
Several topics related to packing on a sphere are discussed: packing points, packing lines through the center, and packing k-flats in dimension d. Two frequently asked questions in the graphics...
Computational Geometry Column 29 (1993)
, 1993. [Sha94] M. Sharir. Almost tight upper bounds for lower envelopes in higher dimensions. Discrete Comput. Geom., 12:327--345, 1994. [SS83] J. T. Schwartz and M. Sharir. On the "piano...
Image analysis of human motion /--Joseph O'Rourke. (1980)
Thesis (Ph. D.)--University of Pennsylvania, 1980.
Representation and display of three dimensional objects with spheres. (1977)
Thesis (M.S. in Computer and Information Sciences)--Graduate School of Arts and Sciences, University of Pennsylvania, 1977.