Organization. My recent papers are listed in two tables, each entry of which links to full bibliographic details in a long list below both. The first table lists regular papers, in reverse chronological order. The second lists my Computational Geometry Columns, again in reverse chronological order. The detailed list into which these two tables links includes buttons to download PDF, and/or compressed Postscript, and perhaps includes a representative figure. If you are looking for a specific paper, you might use Edit/Find in your browser.

File Formats. Most of these papers are now in PDF format (.pdf), or compressed .pdf.gz. The older papers are in gzip'ped Postscript form (file.ps.gz); a few much older ones are in compressed Postscript (file.ps.Z). If your browser has the appropriate plugins, it will automatically gunzip (or uncompress) to file.pdf (or file.ps), and then invoke a PDF/Postscript viewer (e.g., GhostView) to display the paper. Some are linked to Electronic Conference Proceedings, and some are available, in both PDF and Postscript , on the e-print arXiv (CoRR: Computer Science Research Repository).

BibTeX Citations. If you need BibTeX to cite a paper in LaTeX, I have placed them all in this single bib file. You'll have to search for the title through the page (using Find in your browser).

 

Papers

Authors
Title
Year
Luis Barbay, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, J. O'Rourke, Andre van Renssen, Perouz Taslakian, Sander Verdonschot
2013
Stephanie Jakus and J. O'Rourke
2012
J. O'Rourke
2013
Erik D. Demaine, Martin L. Demaine, Jin-ichi Itoh, Anna Lubiw, Chie Nara, Joseph O'Rourke
2012
J. O'Rourke and Mandira Virmani
1991
J. O'Rourke
2011
Nadia Benbernou, Erik Demaine, Martin Demaine, Anastasia Kurdia, J. O'Rourke, Godfried Toussaint, Jorge Urrutia, Giovanni Viglietta
2011
Joseph O'Rourke and Costin Vilcu
2011
J. O'Rourke and Costin Vilcu
2011
J. O'Rourke
2011
J. O'Rourke
2011
J. O'Rourke
2010
J. O'Rourke
1985
L. J. Aupperle and H. E. Conn and J. M. Keil and Joseph O'Rourke
1988
J. O'Rourke
2010
J. O'Rourke
2010
J. O'Rourke
2010
Yonit Bousany, Mary Leah Karker, J. O'Rourke, Leona Sparaco
2010
Prosenjit Bose, Mirela Damian, Karim Douieb, Joseph O'Rourke, Ben Seamone, Michiel Smid, and Stefanie Wurher
2010
Erik Demaine, Martin Demaine, Vi Hart, John Iacono, Stephan Langerman, J. O'Rourke
2009
Jin-ichi Itoh, J. O'Rourke, and Costin Vilcu
2009
J. O'Rourke
2009
Greg Aloupis, Sebastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, J. O'Rourke, Val Pincu, Suneeta Ramaswami, Vera Sacristan, Stefanie Wuhrer
2008
Brad Ballinger, Nadia Benbernou, Francisco Gomez-Martin, J. O'Rourke, Godfried Toussaint
2009
Jin-ichi Itoh, Costin Vilcu, Joseph O'Rourke
2009
J. O'Rourke
2008
Greg Aloupis, Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan Langerman, J. O'Rourke, Belen Palop
2008
Greg Aloupis, Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan Langerman and J. O'Rourke
2008
Stefanie Wuhrer, P. Bose, S. Chang, J. O'Rourke
2008
Alex Benton and J. O'Rourke
2008
J. O'Rourke, Perouz Taslakian and Godfried Toussaint
2008
Zachary Abel, David Charlton, Sebastien Collette, Erik D. Demaine, Martin L. Demaine, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Godfried Toussaint
2008
J. O'Rourke
2008
Mirela Damian, Robin Flatland, J. O'Rourke, Suneeta Ramaswami
2007
J. O'Rourke
2007
Joseph O'Rourke
2007
Jin-ichi Itoh, J. O'Rourke, Costin Vilcu
2007
Mirela Damian, Robin Flatland, J. O'Rourke, Suneeta Ramaswami
2007
J. O'Rourke
2009
Greg Aloupis, Sebastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristan, Stefanie Wuhrer
2009
J. O'Rourke
2007
Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik Demaine, Martin Demaine, Robin Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian and Godfried Toussaint
2007
Alex Benton and Joseph O'Rourke
2007
J. O'Rourke
2007
Erik Demaine and Joseph O'Rourke
2005
Nadia Benbernou and Joseph O'Rourke
2007
Erik Demaine, Blaise Gassend, J. O'Rourke, and Godfried Toussaint
2006
Mirela Damian, Robin Flatland, Joseph O'Rourke
2007
Mirela Damian, Robin Flatland, Henk Meijer, and J. O'Rourke
2005
Erik Demaine and Joseph O'Rourke
2005
Joseph O'Rourke
2005
Mirela Damian, Robin Flatland, Joseph O'Rourke
2007
Mirela Damian, Robin Flatland, Joseph O'Rourke
2006
Julie Glass, Bin Lu, Joseph O'Rourke, Jianyuan K. Zhong
2005
Erik. D. Demaine, Stefan Langermann, J. O'Rourke
2005
Julie Glass, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink, Jianyuan K. Zhong
2004
E. D. Demaine and J. O'Rourke
2004
Greg Aloupis, Erik Demaine, Stefan Langerman, Patrick Morin, J. O'Rourke, Godfried Toussaint, and Ileana Streinu
2004
Mirela Damian and J. O'Rourke
2004
Erik. D. Demaine, Satyan L. Devadoss, Joseph S. B. Mitchell, J. O'Rourke
2004
Nadia Benbernou, Patricia Cahn, J. O'Rourke
2004
J. O'Rourke and Geetika Tewari
2004
Mirela Damian and Joseph O'Rourke
2003
Suzanne Gallagher and J. O'Rourke
2003
Mirela Damian and J. O'Rourke
2003
E. Demaine, J. O'Rourke
2003
Rebecca Alexander, Heather Dyson, J. O'Rourke
2002
E. Demaine, J. O'Rourke
2002
Melody Donoso and Joseph O'Rourke
2002
Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke
2002
E. Demaine, S. Langerman, J. O'Rourke, J. Snoeyink
2002
J. O'Rourke, Octavia Petrovici
2001
E. Demaine, S. Langerman, J. O'Rourke
2001
J. O'Rourke, Irena Pashchenko, Geetika Tewari,
2001
E. Demaine, J. O'Rourke,
2001
T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides
2002
Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke.
2002
Joseph O'Rourke
2001
Joseph O'Rourke
2002
Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke.
2000
Joseph O'Rourke
2000
E. Demaine, M. Demaine, J. O'Rourke
2000
Biliana Kaneva and J. O'Rourke
2000
E. D. Demaine, J. O'Rourke
2000
E. Demaine, M. Demaine, J. O'Rourke
2000
J. O'Rourke and The Smith Problem Solving Group
1999
T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides
1999
J. O'Rourke
1999
Roxana Cocan and J. O'Rourke
1999
E. Demaine, M. Demaine, A. Lubiw, J. O'Rourke, I. Pashchenko
1999
J. O'Rourke and Irena Pashchenko
1998
J. O'Rourke
1998
Therese Biedl, Erik Demaine, Martin Demaine, Anna Lubiw, Mark Overmars, Joseph O'Rourke, Steve Robbins, Sue Whitesides
1998
J. O'Rourke
1997
P. Agarwal, B. Aronov, J. O'Rourke, C. Schevon
1997
A. Lubiw, J. O'Rourke,
1996
J. O'Rourke, I. Streinu
1996
C. Gitlin, J. O'Rourke, V. Subramanian
1996
J. O'Rourke, T. Shermer, I. Streinu
1995
V. Estivill-Castro, J. O'Rourke, J. Urrutia, D. Xu
1995

 

Computational Geometry Columns

Authors
Column #
Abstract
Year
J. O'Rourke

Two art-gallery-like problems concerning transmitters in polygons are described, and several open problems posed.
2012
J. O'Rourke

Can a simple spherical polygon always be triangulated? The answer depends on the definitions of ``polygon'' and ``triangulate.''
2008
J. O'Rourke

Two long-open problems have been solved: (1) every sufficiently large planar point set in general position contains the vertices of an empty hexagon; (2) every finite collection of polygons of equal area have a common hinged dissection.
2008
J. O'Rourke

The new algorithm of Bobenko and Izmestiev for reconstructing the unique polyhedron determined by given gluings of polygons is described.
2007
J. O'Rourke

A new class of art gallery -like problems inspired by wireless localization is discussed.
2006
J. O'Rourke

A remarkable theorem is described: "It is possible to tile the plane with non-overlapping squares using exactly one square of each integral dimension.'' Thus, one can "square the plane.''
2006
J. O'Rourke

The old problem of determining the chromatic number of the plane is revisited.
2004
J. O'Rourke

The algorithm of Edelsbrunner for surface reconstruction by "wrapping" a set of points in R^3 is described.
2004
J. O'Rourke

The open problem of whether or not every pair of equal-area polygons has a hinged dissection is discussed.
2003
J. O'Rourke

The concept of pointed pseudo-triangulations is defined and a few of its applications described.
2002
J. S. B. Mitchell and J. O'Rourke

A compendium of thirty previously published open problems in computational geometry is presented.
2001
J. O'Rourke

The recent result that n congruent balls in R^d have at most 4 distinct geometric permutations is described.
2001
Joseph O'Rourke

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.
2000
Joseph O'Rourke

The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
2000
J. O'Rourke

Recent results on curve reconstruction are described.
2000
E. Demaine, J. O'Rourke

Open problems from the 15th Annual ACM Symposium on Computational Geometry.
1999
J. O'Rourke

Two results in ``computational origami'' are illustrated.
1999
J. O'Rourke

The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.
1999
P. K. Agarwal, J. O'Rourke

Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.
1998
J. O'Rourke

Several recent SIGGRAPH papers on surface simplification are described.
1998
J. O'Rourke

The proof of Dey's new k-set bound is illustrated.
1997
J. O'Rourke

Several topics related to packing on a sphere are discussed: packing points, packing lines through the center, and packing k-flats in dimension d.
1997
J. O'Rourke

Several results from Combinatorial Geometry by J. Pach and P.K. Agarwal are detailed.
1997
J. O'Rourke

Past accomplisments of Computational Geometry are reviewed and future directions adumbrated.
1996

 

Bibliographic Details

Click on the PDF icon to download PDF (.pdf or .pdf.gz).
Click on the PS icon to download Postscript (.ps or .ps.gz or .ps.Z).
Mouse over the FIG icon to show a thumbnail figure; some show a larger figure when the FIG icon is clicked.
  • New and improved spanning ratios for Yao graphs
      Luis Barbay, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, J. O'Rourke, Andre van Renssen, Perouz Taslakian, Sander Verdonschot
      Submitted, July 2013.



  •  
  • From Pop-Up Cards to Coffee-Cup Caustics: The Knight's Visor




  • Unfolding Face-Neighborhood Convex Patches: Counterexamples and Positive Results
      J. O'Rourke
      Canadian Conference on Computational Geometry
      To appear, Aug 2013.





  • Computational Geometry Column 52
      J. O'Rourke
      SIGACT News, Vol. 43, No. 1, Mar. 2012.

  •  

  • Refold Rigidity of Convex Polyhedra
      Erik D. Demaine, Martin L. Demaine, Jin-ichi Itoh, Anna Lubiw, Chie Nara, Joseph O'Rourke
      EuroCG 2012, Assisi, Italy, Mar 2012.
      4-page Abstract: pp. 273-276.
      Journal version: Computational Geometry: Theory and Applications, \46 (2013), pp. 979-989.





  • Generating Random Polygons
      J. O'Rourke and Mandira Virmani
      Smith Technical Report 011, July 1991.
      [Scanned.]

  •  

  • Common Edge-Unzippings for Tetrahedra




  • Edge-guarding Orthogonal Polyhedra
      Nadia Benbernou, Erik Demaine, Martin Demaine, Anastasia Kurdia, J. O'Rourke, Godfried Toussaint, Jorge Urrutia, Giovanni Viglietta
      Accepted to 23rd Canadian Conference on Computational Geometry, (Toronto), May 2011.





  • Development of Curves on Polyhedra via Conical Existence
      Joseph O'Rourke and Costin Vilcu
      23rd Canadian Conference on Computational Geometry (Toronto), pp. 71-76, Aug. 2011.
      Revised for journal submission, Sep. 2001. This paper now incorporates many of the results from the arXiv paper, "Conical Existence of Closed Curves on Convex Polyhedra."





  • Conical Existence of Closed Curves on Convex Polyhedra
      J. O'Rourke and Costin Vilcu
      arXiv:1102.0823 [cs.DM]
      3 Feb. 2011. Version 2: 14 Feb. 2011.
      Accepted to Computational Geometry: Theory & Applications, 2013.





  • String-wrapped Rotating Disks
      J. O'Rourke
      XIV Spanish Mtg. Comput. Geom. Centre de Recerca Matemática, Alcalá de Henares, June 2011, pp. 63-66.
      Revised, full version for LNCS volume: 7 May 2012.





  • Convex Polyhedra Realizing Given Face Areas




  • A Note on Solid Coloring of Pure Simplicial Complexes




  • Finding Minimal Enclosing Boxes
      J. O'Rourke
      International Journal of Computer and Information Sciences, 14(3), pp. 183-199.

  •  

  • Covering orthogonal polygons with squares
      L. J. Aupperle and H. E. Conn and J. M. Keil and Joseph O'Rourke
      Proc. 26th Allerton Conf. Commun. Control Comput., pp. 97-106, 1988.

  •  

  • Flat Zipper-Unfolding Pairs for Platonic Solids
  •  

  • On Folding a Polygon to a Polyhedron




  • On Flat Polyhedra deriving from Alexandrov's Theorem




  • Sweeping Minimum Perimeter Enclosing Parallelograms: Optimal Crumb Cleanup
      Yonit Bousany, Mary Leah Karker, J. O'Rourke, Leona Sparaco
      Accepted to Canadian Conference on Computational Geometry, August 2010, to appear.





  • π/2-angle Yao graphs are spanners
      Prosenjit Bose, Mirela Damian, Karim Douieb, Joseph O'Rourke, Ben Seamone, Michiel Smid, and Stefanie Wurher
      Proc. 21st Internat. Symp. Algorithms Computation (ISAAC), Part II, Lecture Notes in Computer Science, Volume 6507, pages 446-457, Springer, Dec. 2010.
      Preliminary version: arXiv: 1001.2913v1 [cs.CG], January 2010.





  • Continuous Blooming of Convex Polyhedra
      Erik Demaine, Martin Demaine, Vi Hart, John Iacono, Stephan Langerman, J. O'Rourke
      arXiv:0906.2461v1 [cs.CG]. June 2009.
      Accepted to The 7th Japan Conference on Computational Geometry and Graphs, Aug. 2009.





  • Source unfoldings of convex polyhedra with respect to certain closed polygonal curves
      Jin-ichi Itoh, J. O'Rourke, and Costin Vilcu
      Proc. 25th European Workshop Comput. Geom. (EuroCG)
      pp. 61-64, March 2009.
      Full version submitted to journal. PDF link is to full version.
      See also the companion paper. Full paper arXiv:1205.0963v1 [cs.CG] 4May12.





  • Some Properties of Yao Y4 Subgraphs




  • Realistic Reconfiguration of Crystalline (and Telecube) Robots
      Greg Aloupis, Sebastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, J. O'Rourke, Val Pincu, Suneeta Ramaswami, Vera Sacristan, Stefanie Wuhrer
      Workshop on Algorithmic Foundations of Robotics (WAFR).
      Guanajuato, Mexico, Dec. 2008.

  •  

  • The Continuous Hexachordal Theorem
      Brad Ballinger, Nadia Benbernou, Francisco Gomez-Martin, J. O'Rourke, Godfried Toussaint
      Internat. Conf. on Mathematics and Computation in Music (MCM 2009), to appear, June 2009.





  • Star Unfolding Convex Polyhedra via Quasigeodesic Loops
      Jin-ichi Itoh, Costin Vilcu, Joseph O'Rourke
      Discrete & Computational Geometry, 44(1) July 2010, pp. 35-54.
      Earlier version: arXiv:0707.4258v4 [cs.CG]
      See also the companion paper.
      See also preliminary version "Unfolding Convex Polyhedra via Quasigeodesics" below, and Technical Report 091, Smith College, December 2008.





  • Computational Geometry Column 51
      J. O'Rourke
      SIGACT News, Vol. 43, No. 3, Sept. 2008.
      Internat. J. Comp. Geom. & Appl., 2008. To appear.

  •  

  • Unfolding Polyhedra
      J. O'Rourke
      Submitted for publication, July 2008.





  • Highway Hull Revisited
      Greg Aloupis, Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan Langerman, J. O'Rourke, Belen Palop
      Submitted, June 2008. Revised, April 2009. arXiv:0806.1416v1 [cs.CG]

  •  

  • Draining a Polygon--or--Rolling a Ball out of a Polygon
      Greg Aloupis, Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan Langerman and J. O'Rourke
      20th Canadian Conference on Computational Geometry, Montreal, Aug. 2008.

  •  

  • Morphing of Triangular Meshes in Shape Space
      Stefanie Wuhrer, P. Bose, S. Chang, J. O'Rourke
      20th Canadian Conference on Computational Geometry, Montreal, Aug. 2008.
      Revised, full version, Nov. 2009, available by request.

  •  

  • A Class of Convex Polyhedra with Few Edge Unfoldings
      Alex Benton and J. O'Rourke
      20th Canadian Conference on Computational Geometry, Montreal, Aug. 2008.
      Earlier version: Smith Technical Report 089.
      arXiv:0801.4019v1 [cs.CG]





  • A Pumping Lemma for Homometric Rhythms
      J. O'Rourke, Perouz Taslakian and Godfried Toussaint
      20th Canadian Conference on Computational Geometry, Montreal, Aug. 2008.

  •  

  • Cauchy's Arm Lemma on a Growing Sphere
      Zachary Abel, David Charlton, Sebastien Collette, Erik D. Demaine, Martin L. Demaine, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Godfried Toussaint
      Smith Technical Report, April 2008.
      arXiv.0804.0986v1 [cs.CG]

  •  

  • Computational Geometry Column 50
      J. O'Rourke
      SIGACT News, Vol. 39, No. 1, March 2008, pp. 73-76.
      Internat. J. Comp. Geom. & Appl.. To appear.

  •  

  • Edge-Unfolding Medial Axis Polyhedra
      J. O'Rourke
      24th European Workshop on Computational Geometry, Nancy, France, March 2008, pp. 103-106.





  • A new lower bound on guard placement for wireless localization
      Mirela Damian, Robin Flatland, J. O'Rourke, Suneeta Ramaswami
      2-page abstract in Fall Workshop on Computational Geometry, Nov. 2007, pp. 13-14.





  • Band Unfoldings and Prismatoids: A Counterexample
  •  

  • Unfolding Restricted Convex Caps




  • Unfolding Convex Polyhedra via Quasigeodesics
      Jin-ichi Itoh, J. O'Rourke, Costin Vilcu
      Smith Computer Science Technical Report 085, July;
      arXiv:0707.4258v3 [cs.CG]. Also: 2-page abstract in Fall Workshop on Computational Geometry, Nov. 2007., pp. 79-80.





  • Connecting Polygonizations via Stretches and Twangs
      Mirela Damian, Robin Flatland, J. O'Rourke, Suneeta Ramaswami
      Theory of Computer Systems, To appear, 2009. DOI 10.1007/s00224-009-9192-8.
      Preliminary version: 25th Symposium on Theoretical Aspects of Computer Science (STACS), Bordeaus, Feb. 2008, pp. 217-228, IBFI Schloss Dagstuhl.
      See also: arXiv:0709.1942v1 [cs.CG].
      2-page abstract in 17th Fall Workshop on Computational Geometry, Nov. 2007, pp. 85-86.
      See also Twang Cascades, the Movie.





  • Folding Polygons to Convex Polyhedra
      J. O'Rourke
      In National Council of Teachers of Mathematics (NCTM) 71st Yearbook: Understanding Geometry for a Changing World, pp. 77-87, 2009.





  • Linear Reconfiguration of Cube-Style Modular Robots
      Greg Aloupis, Sebastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristan, Stefanie Wuhrer
      Computational Geometry: Theory and Applications, 42(6-7):652-663, Aug. 2009 Preliminary version: International Symposium on Algorithms and Computation (ISSAC) Dec. 2007, Lecture Notes in Computer Science, Vol. 4835/2007, 208-219.

  •  

  • Unfolding Orthogonal Terrains
      J. O'Rourke
      Smith Technical Report 084, July 2007. arXiv:0707.0610v4 [cs.CG]. See also Animations.





  • Computational Geometry Column 49
      J. O'Rourke
      SIGACT News, Vol. 38, No. 2, Issue 143, June 2007, pp. 55-59.





  • Vertex Pops and Popturns
      Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik Demaine, Martin Demaine, Robin Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian and Godfried Toussaint
      Accepted to Canadian Conference on Computational Geometry, Ottawa, Aug. 2007.

  •  

  • Unfolding Polyhedra via Cut-Tree Truncation
      Alex Benton and Joseph O'Rourke
      Accepted to Canadian Conference on Computational Geometry, Ottawa, Aug. 2007.





  • Unfolding Orthogonal Polyhedra
      J. O'Rourke
      Proceedings of the Snowbird Conference Discrete and Computational Geometry: Twenty Years Later, Eds. J.E. Goodman, J. Pach, R. Pollack. American Mathematical Society, to appear, 2007.

  •  

  • Comptutational Geometry Column 48
      J. O'Rourke
      SIGACT News, Vol. 37, No. 3, Issue 140, Sept 2006, pp. 55-57.





  • Computational Geometry Column 47
      J. O'Rourke
      SIGACT News, Vol. 37, No. 2, Issue 139, June 2006, pp. 47-49.

  •  

  • A Survey of Folding and Unfolding in Computational Geometry
      Erik Demaine and Joseph O'Rourke
      Combinatorial and Computational Geometry. Eds. Jacob E. Goodman, Janos Pach, Emo Welzl, Mathematical Sciences Research Institute Publications, Vol. 52, Cambridge University Press, 2005, pp. 167-211.

  •  

  • On the Maximum Span of Fixed-Angle Chains
      Nadia Benbernou and Joseph O'Rourke
      Full version arXiv:0801.0258v1 [cs.CG], Dec. 2007, supercedes 4-page version: 18th Canadian Conference on Computational Geometry.
      Submitted, Dec. 2007. Kingston, August, 2006.





  • Polygons Flip Finitely: Flaws and a Fix
      Erik Demaine, Blaise Gassend, J. O'Rourke, and Godfried Toussaint
      18th Canadian Conference on Computational Geometry, Kingston, August, 2006.

  •  

  • Epsilon-Unfolding Orthogonal Polyhedra
      Mirela Damian, Robin Flatland, Joseph O'Rourke
      Graphs and Combinatorics 23[Suppl], 179-194, 2007. Replaces earlier version arXiv cs.CG/0602095, Feb. 2006.





  • Unfolding well-separated orthotrees
      Mirela Damian, Robin Flatland, Henk Meijer, and J. O'Rourke
      15th Annual Fall Workshop on Computational Geometry, University of Pennsylvania, Nov. 2005, pp. 23-25.

  •  

  • Open Problems from CCCG 2004
      Erik Demaine and Joseph O'Rourke
      17th Canadian Conference on Computational Geometry, Windsor, August 2005, pp. 303-306.

  •  

  • Polygonal chains: from Pocket Flipping to Protein Folding
      Joseph O'Rourke
      17th Canadian Conference on Computational Geometry, Aug. 2005, Windsor, Ontario.

  •  

  • Unfolding Manhattan Towers
      Mirela Damian, Robin Flatland, Joseph O'Rourke
      Computational Geometry: Theory & Applications, Vol. 40, No. 2, July 2008, pp. 102-114.
      Preliminary version: 17th Canadian Conference on Computational Geometry, Aug. 2005, Windsor, Ontario, pp. 211-214. See also Animations.





  • Grid Vertex-Unfolding Orthogonal Polyhedra
      Mirela Damian, Robin Flatland, Joseph O'Rourke
      Discrete Comput. Geom., Vol. 39, No. 1-3, pp. 213-238, 2008.
      DOI 10.1007/s00454-007-9043-9.
      Supercedes earlier versions: cs.CG/0509054, September 2006, which supercedes the preliminary version that appeared in 23rd Annu. Sympos. Theoretical Aspects Comput. Sci. (STACS), Marseille, France. Lecture Notes in Computer Science, Volume 3884, Springer, Berlin/Heidelberg, Feb. 2006, pp. 264-276.





  • A 2-chain can interlock with an open 11-chain
      Julie Glass, Bin Lu, Joseph O'Rourke, Jianyuan K. Zhong
      Geombinatorics, 15(4), Apr. 2006, pp. 166-176.





  • Geometric restrictions on producible polygon protein chains
      Erik. D. Demaine, Stefan Langermann, J. O'Rourke
      Lecture Notes in Computer Science, Vol. 2906, Springer-Verlag, Nov 2003, pp. 395-404. Algorithmica, Vol. 44, No. 2, 167-181, Feb. 2006.





  • A 2-chain can interlock with a k-chain
      Julie Glass, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink, Jianyuan K. Zhong
      Smith College Technical Report 079, arXiv. See also model photos.





  • Open Problems from CCCG 2003
      E. D. Demaine and J. O'Rourke
      16th Canadian Conference on Computational Geometry, Concordia, August 2004, pp. 209-211

  •  

  • Edge-Unfolding Polyhedral Bands
      Greg Aloupis, Erik Demaine, Stefan Langerman, Patrick Morin, J. O'Rourke, Godfried Toussaint, and Ileana Streinu
      Computational Geometry: Theory and Applications, Vol. 39, No. 1, Jan. 2008, pp. 30-42.
      Preliminary version: 16th Canadian Conference on Computational Geometry, Concordia, August 2004, pp. 60-63.

  •  

  • On Corners of Objects Built from Parallelepiped Bricks
      Mirela Damian and J. O'Rourke
      Computational Geometry: Theory & Applications, Vol. 40, No. 2, July 2008, pp. 102-114.
      Preliminary version 16th Canadian Conference on Computational Geometry, Concordia, August 2004,

  •  

  • Continuous Foldability of Polygonal Paper
      Erik. D. Demaine, Satyan L. Devadoss, Joseph S. B. Mitchell, J. O'Rourke
      16th Canadian Conference on Computational Geometry, Aug. 2004, pp. 64-66.

  •  

  • Computational Geometry Column 46
      J. O'Rourke
      SIGACT News, Vol. 35, No. 3, Sep. 2004, pp. 42-45.





  • Unfolding Smooth Primsatoids
      Nadia Benbernou, Patricia Cahn, J. O'Rourke
      arXiv cs.CG/0407063
      Smith College Computer Science Technical Report 078, July 2004





  • Computational Geometry Column 45
      J. O'Rourke
      SIGACT News, Vol. 35, No. 2, Jun 2004, Issue 131, pp. 71-74; Internat. J. Comput. Geom. Appl., to appear.





  • The Structure of Optimal Partitions of Orthogonal Polygons into Fat Rectangles
      J. O'Rourke and Geetika Tewari
      Computational Geometry: Theory and Applications, Vol. 28, No. 1, pp. 49-71, 2004.





  • A Note on Objects Built from Bricks
      Mirela Damian and Joseph O'Rourke
      Smith College Technical Report, July 2003, arXiv cs.CG/0307042.





  • Coloring Objects Built from Bricks
      Suzanne Gallagher and J. O'Rourke
      15th Canadian Conference on Computational Geometry, Halifax, August 2003, pp. 56-59.







  •   "Partitioning Regular Polygons into Circular Pieces I: Convex Partitions."
      Mirela Damian and J. O'Rourke
      15th Canadian Conference on Computational Geometry, Halifax, August 2003, pp. 43-46.
      Full version: Retrieve from CoRR: get paper cs.CG/0304023



  •  
  •  "Computational Geometry Column 44,"
      J. O'Rourke
      Int. J. Comp. Geom. Appl., to appear.
      SIGACT News, to appear.
      The open problem of whether or not every pair of equal-area polygons has a hinged dissection is discussed.
      (See also The Open Problems Project, Problem 47.)
      Retrieve from CoRR: get paper cs.CG/0304025

  •  

  •   "Open Problems from CCCG 2002"
      E. Demaine, J. O'Rourke
      in Proc. of the 15th Canadian Conference on Computational Geometry, Halifax, August 2003, pp. 178-181.
      Retrieve from CoRR: get paper cs.CG/0212050

  •  

  •   "The Convex Polyhedra Foldable from a Square"
      Rebecca Alexander, Heather Dyson, J. O'Rourke
      DIMACS Workshop on Computational Geometry, 14-15 Nov 2002. Abstract (2 pages)
      Japan Conference on Discrete and Computational Geometry, Tokyo, Dec. 2002, pp. 31-32.
      Springer-Verlag LNCS proceedings, to appear, 2003.





  •   "Open Problems from CCCG 2001"






  •   "Computational Geometry Column 43,"
      J. O'Rourke
      Int. J. Comp. Geom. Appl., Vol. 12, No. 3 (2002): 263-265.
      SIGACT News, 33(1) Issue 122, Mar. 2002, 58-60.
      The concept of pointed pseudo-triangulations is defined and a few of its applications described.
      Retrieve from CoRR: get paper cs.CG/0203008





  •  
  •  "Nonorthogonal Polyhedra Built from Rectangles"
      Melody Donoso and Joseph O'Rourke
      Smith Technical Report 073, 29 Oct 2001; Revised 7 May 2002.
      Retrieve from CoRR: get paper cs.CG/0110059

  •  

     
  •  "Vertex-Unfoldings of Simplicial Manifolds "
      Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke
      18th ACM Symposium on Computational Geometry, Barcelona, June 2002, pp. 237-243.
      This paper is now available in three versions, each of which supercedes the previous.
      Naturally we prefer you only look at the latest version, in Discrete Geometry, ed. Andras Bezdek, Marcel Dekker, New York, 2003, pp. 215-228.
      Earlier versions available at CoRR:

  •  



  •  "Interlocked Open Linkages with Few Joints"
      E. Demaine, S. Langerman, J. O'Rourke, J. Snoeyink
      18th ACM Symposium on Computational Geometry, Barcelona, June 2002, pp. 189-198.

  •  

  •  "Computational Geometry Column 42,"
      J. S. B. Mitchell and J. O'Rourke
      Int. J. Comp. Geom. Appl., Vol. 11, No. 5 (2001) 573-582.
      SIGACT News, 32(3) Issue 120, Sep. 2001, 63-72.
      A compendium of thirty previously published open problems in computational geometry is presented.
      (See also The Open Problems Project.)
      Retrieve from CoRR: get paper cs.CG/0108021

  •  

     
  •   "Narrowing Light Rays with Mirrors"
  •  

     
  •  "Short Interlocked Linkages"
  •  

     
  •   "Partitioning Orthogonal Polygons into Fat Rectangles"
  •  

     
  •   "Open Problems from CCCG 2000"
  •  

     
  •   "A Note On Reconfiguring Tree Linkages: Trees can Lock."
      T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides
      Discrete and Applied Mathematics, 117 (2002) 293--297.
      (Based on abstract published in 10th Canad. Conf. Comput. Geom., Aug. 1998, 4-5.)
      CiteSeer citations

  •  

     
  •   "Computational Geometry Column 41,"
      J. O'Rourke
      Int. J. Comp. Geom. Appl., Vol. 11, No. 2 (2001) 239-242.
      SIGACT News, 32(1) Issue 118 Mar. 2001, 53-55.
      The recent result that n congruent balls in R^d have at most 4 distinct geometric permutations is described.
      Retrieve from CoRR: get paper cs.CG/0102004

  •  

     
  •   "Enumerating Foldings and Unfoldings between Polygons and Polytopes."
      Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke.
      Graphs and Combinatorics 18(1) 93-104 (2002).
      Revised version of Japan Conference on Discrete and Computational Geometry,
      Tokyo, Nov. 2000, pp. 9-12.
      Retrieve from CoRR: get paper cs.CG/0107024
      See also the longer Technical Report below.

  •  

     
  •   "An Extension of Cauchy's Arm Lemma with Application to Curve Development"
      Joseph O'Rourke
      Lecture Notes Comput. Sci. Vol. 2098, eds. J. Akiyama, M. Kano, M. Urabe, Springer-Verlag, Berlin, 2001, pp. 280-291.
      Revised version of Japan Conference on Discrete and Computational Geometry,
      Tokyo, Nov. 2000, pp. 65-67.
      (This paper is a revised version of the first half of the Technical Report below.)

  •  

     
  •   "On the Development of the Intersection of a Plane with a Polytope"
      Joseph O'Rourke
      Computational Geometry: Theory and Applications, to appear, 2002.
      (This paper is a revised version of the second half of the Technical Report below. Revised Jan. 2002.)

  •  

     
  •  "Computational Geometry Column 40,"
      Joseph O'Rourke
      Int. J. Comp. Geom. Appl., 10:6 (2000) 649-651.
      SIGACT News, 31(4), (Issue 117) December 2000, 62-64.
      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.
      Retrieve from CoRR: get paper cs.CG/0010039

  •  

     
  •  "Computational Geometry Column 39,"
      Joseph O'Rourke
      Int. J. Comp. Geom. Appl., 10(4) (2000) 441-444.
      SIGACT News 31(3): 47-49 (2000)
      The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
      Retrieve from CoRR: get paper cs.CG/0007042

  •  

     
  •  "Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes."
      Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke.
      Smith Tech. Rep. 069, July 2000 (54 pages).
      See also the later LNCS paper above.
      Retrieve from CoRR: get paper cs.CG/0007019

  •  

     
  •  "On the Development of the Intersection of a Plane with a Polytope"
  •  

  •  "PushPush and Push-1 are NP-hard in 2D."
      E. Demaine, M. Demaine, J. O'Rourke
      in Proc. of the 12th Canadian Conference on Computational Geometry, New Brunswick, August 2000, pp. 211-219.
      Retrieve from CoRR: get paper cs.CG/0007021
      CiteSeer citations

  •  

     
  •  "An Implementation of Chen & Han's Shortest Paths Algorithm"
      Biliana Kaneva and J. O'Rourke
      in Proc. of the 12th Canadian Conference on Computational Geometry, New Brunswick, August 2000, pp. 139-146. .
      See also our gallery of examples

  •  

     
  •  "Open Problems from CCCG'99"
  •  

     
  •  "Computational Geometry Column 38"
      J. O'Rourke
      Int. J. Comp. Geom. Appl., 10(2): 221-223 (2000).
      SIGACT News, Vol. 31. No. 1, (Whole Number 114), March 2000, pp. 28-30.
      Recent results on curve reconstruction are described.
      Retrieve from CoRR: get paper cs.CG/0001025

  •  

     
  •  "PushPush is NP-hard in 2D."
      E. Demaine, M. Demaine, J. O'Rourke
      Smith Tech. Rep. 065, Jan. 2000.
      Retrieve from CoRR: get paper cs.CG/000101

  •  

     
  •  "PushPush is NP-hard in 3D."
      J. O'Rourke and The Smith Problem Solving Group
      Smith Tech. Rep. 064, Jan. 2000.
      Retrieve from CoRR: get paper cs.CG/9911013

  •  

     
  •  "Locked and Unlocked Polygonal Chains in 3D."
      T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides
      Journal version: Discrete and Computational Geometry. 26(3), pp. 269-281, Oct. 2001. Abstract (2 pages):
      Proc. 10th ACM-SIAM Sympos. Discrete Algorithms, Jan. 1999, pp. 866-7.
      Retrieve from CoRR: get paper cs.CG/9811019;
      Full version (29 pages): Smith Tech. Rep. 060, October 1999.
      Retrieve from CoRR: get paper cs.CG/9910009

  •  

     
  •  "Folding and unfolding in computational geometry"
      J. O'Rourke
      Lecture Notes Comput. Sci.. Vol. 1763, Springer-Verlag, Berlin, 2000, pp. 258-266.
      Revised version of Proc. Japan Conf. Discrete Comput. Geom. '98, Dec. 1998, pp. 142-147.
      CiteSeer citations

  •  

     
  •  "Polygonal Chains Cannot Lock in 4D."
      Roxana Cocan and J. O'Rourke
      Final journal version: Comput. Geom. Theory Appl., 20 (2001) 105-129.
      Abstract (4 pages) in Proc. of the 11th Canadian Conference on Computational Geometry, Vancouver, August 1999, pp.5-8.
      Full version (29 pages): Smith Tech. Rep. 063, Aug 1999; revised 2 Feb 2001:
      Retrieve from CoRR: get paper cs.CG/9908005
      CiteSeer citations

  •  

     
  •  "Computational Geometry Column 37"
      E. Demaine, J. O'Rourke
      Int. J. Comp. Geom. Appl., 10(1) 103-107 (2000).
      SIGACT News 30(3), Issue #112 (Sep. 1999) 39-42.
      Open problems from the 15th Annual ACM Symposium on Computational Geometry.
      Retrieve from CoRR: get paper cs.CG/9908007

  •  

     
  •  "Metamorphosis of the Cube,"
      E. Demaine, M. Demaine, A. Lubiw, J. O'Rourke, I. Pashchenko
      Proc. 15th Annu. ACM Sympos. Comput. Geom. 1999, pp. 409-410.

  •  

     
  • "Computational Geometry Column 36"
      J. O'Rourke
      SIGACT News 30(3), Issue #112 (Sep. 1999) 35-38. Int. J. Comp. Geom. Appl., 9(6) 615-618 (1999).
      Two results in ``computational origami' are illustrated.

  •  

     
  •  "Computational Geometry Column 35"
      J. O'Rourke
      SIGACT News 30(2), Issue #111 (1999) 31-32.Int. J. Comp. Geom. Appl., 9(4-5) (1999) 513-515.
      The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.

  •  

     
  • "Zero-Parity Stabbing Information"
      J. O'Rourke and Irena Pashchenko
      Japan Conference on Discrete and Computational Geometry, Tokyo, Dec. 1998, pp. 93-97.

  •  

     
  • "Open problems in the combinatorics of visibility and illumination"
      J. O'Rourke
      in Advances in Discrete and Computational Geometry
      eds. B. Chazelle and J. E. Goodman and R. Pollack, (Contemporary Mathematics) American Mathematical Society, Providence, 1998, pp. 237-243.
      Recent Solutions to Open Problems

  •  

     
  • "Unfolding Some Classes of Orthogonal Polyhedra,"
      Therese Biedl, Erik Demaine, Martin Demaine, Anna Lubiw, Mark Overmars, Joseph O'Rourke, Steve Robbins, Sue Whitesides
      10th Canad. Conf. Comput. Geom., Aug. 1998., abs:70-71.
      Retrieve from Electronic Proceedings.
      For 2003 version, download PDF.

  •  

  • "Computational Geometry Column 34"
      P. K. Agarwal, J. O'Rourke
      SIGACT News 29(3) (Issue 108) 27-32, Sept. 1998. Int. J. Comp. Geom. Appl. to appear.
      Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.

  •  

     
  • "Computational Geometry Column 33"
      J. O'Rourke
      SIGACT News 29(2), Issue #107 (1998) 14-16; Int. J. Comp. Geom. Appl., 8(3) (1998) 381-4.
      Several recent SIGGRAPH papers on surface simplification are described.

  •  

     
  • "Computational Geometry Column 32"
      J. O'Rourke
      SIGACT News 28(3), Issue #104 (1997) 12-16; Int. J. Comp. Geom. Appl., 7(5) (1997) 509-513.
      The proof of Dey's new k-set bound is illustrated.

  •  

     
  • "Vertex pi-lights for monotone mountains,"
      J. O'Rourke
      9th Canad. Conf. Comput. Geom., Aug. 1997, pp. 1-5.







  • "Computational Geometry Column 31"
      J. O'Rourke
      SIGACT News Issue #103 28(2), 20-23 (1997); Int. J. Comp. Geom. Appl.,7(4) 379-382 (1997)
      Several topics related to packing on a sphere are discussed: packing points, packing lines through the center, and packing k-flats in dimension d.

  •  

     
  • "Computational Geometry Column 30"
      J. O'Rourke
      SIGACT News Issue #102 28(1), 7-8 (1997); Int. J. Comp. Geom. Appl.,7 165-166 (1997)
      Several topics related to packing on a sphere are discussed: packing points, packing lines through the center, and packing k-flats in dimension d.

  •  

     
  • "Computational Geometry Column 29"
      J. O'Rourke
      SIGACT News Issue #100 27(3) 55-59 1996; Int. J. Comp. Geom. Appl.,6(4) 507-511 (1996)
      Past accomplisments of Computational Geometry are reviewed and future directions adumbrated.

  •  

     
  • "Star unfolding of a polytope with applications,"
      P. Agarwal, B. Aronov, J. O'Rourke, C. Schevon
      SIAM. J. on Computing, 26(6) 1689-1713, December 1997.
      CiteSeer citations

  •  

     
  • "When can a polygon fold to a polytope?,"
      A. Lubiw, J. O'Rourke,
      Smith Tech. Rep. 048, June 1996. AMS Conference, Oct. 1996, Lawrenceville, NJ.
      CiteSeer citations

  •  

     
  • "The Vertex-Edge Visibility Graph of a Polygon,"
      J. O'Rourke, I. Streinu
      Smith Tech. Rep. 047, June 1996; revised Feb. 1997. To appear in Comput. Geom. Theory Appl., 1997.

  •  

     
  • "On reconstruction of polyhedra from parallel slices,"
      C. Gitlin, J. O'Rourke, V. Subramanian
      International Journal of Computational Geometry & Applications, 6(1) 1996, 103-122.

  •  

     
  • "Illuminating convex polygons with vertex floodlights,"
      J. O'Rourke, T. Shermer, I. Streinu
      Proceedings of the Canadian Conference Computational Geometry, (August 1995), 151-156.

  •  

     
  • "Illumination of Polygons with Vertex Lights,"
      V. Estivill-Castro, J. O'Rourke, J. Urrutia, D. Xu
      Information Processing Letters, 56 (1995) 9-13.

  •