EvolvingPolycubes

Joseph O'Rourke

Computational Geometry
Philosophy of Artificial Intelligence
Arts & Technology

Computational Geometry is a relatively new field concerned with designing algorithms and computer programs to perform geometric computations. A need for such computations arises in many fields: computer graphics, robotics, pattern recognition, geography, manufacturing, protein folding, and so on. My own work has leaned toward the theoretical, rather than applied end of the spectrum of possibilities. I started my career with a focus on visibility algorithms, which led to the monograph Art Gallery Theorems and Algorithms. Most recently, I have concentrated on folding & unfolding, which led to a second monograph Geometric Folding Algorithms: Linkages, Origami, Polyhedra. In between I've been interested in the full range of topics covered in my first textbook, the Handbook I co-edited, and a second coauthored textbook. See my full list of papers here.

Here is one of my recent forays into math & art that I find somehow calming:

Gears13
Thirteen Gears (© Joseph O'Rourke 2013)

To give some flavor of the research I pursue with students, I will list the most recent Honors Theses projects I have supervised, several of which led to published papers. (I don't mean to slight the work I do in Special Studies or Summer Projects with other students. See the full list of publications below.)

I also do some research in the philosophy of Artificial Intelligence. I have coauthored three reviews with students in this area. My main focus has been the question of whether or not computers will ever be conscious.

Publications with Students

All of my italicized coauthors listed in the publications below were Smith undergraduates at the time (or in a few recent cases, "post-baccs"). [See my homepage for other, downloadable papers.]

In Computational Geometry

"Sweeping Minimum Perimeter Enclosing Parallelograms: Optimal Crumb Cleanup." Yonit Bousany, Mary Leah Karker, J. O'Rourke, Leona Sparaco. Submitted to the Canadian Conference on Computational Geometry, May 2010.

Nadia Benbernou ('06) and J. O'Rourke, "On the Maximum Span of Fixed-Angle Chains," 18th Canadian Conference on Computational Geometry, Kingston, August, 2006. Submitted for journal publication, 2007.

Nadia Benbernou ('06), Patricia Cahn ('06), and J. O'Rourke, "Unfolding Smooth Primsatoids," 14th Annual Fall Workshop on Computational Geometry, Cambridge, Massachusetts, Nov. 2004, pp. 12-13. arXiv cs.CG/0407063.

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

Suzanne Gallagher ('03) and J. O'Rourke, "Coloring Objects Built from Bricks," 15th Canadian Conference on Computational Geometry, Halifax, August 2003.

Rebecca Alexander ('04), Heather Dyson ('04), Joseph O'Rourke, "The Convex Polyhedra Foldable from a Square," Japan Conference on Discrete and Computational Geometry, Tokyo, Dec. 2002. To appear in Lecture Notes Comput. Sci., Springer-Verlag. Also, DIMACS Workshop on Computational Geometry, Nov. 14-15, 2002.

Joseph O'Rourke and Geetika Tewari ('02). "Partitioning Orthogonal Polygons into Fat Rectangles in Polynomial Time" Submitted to 14th Canadian Conference on Computational Geometry, Lethbridge, Alberta, August 2002.

Melody Donoso ('04) and Joseph O'Rourke. "Nonorthogonal Polyhedra Built from Rectangles". Smith Technical Report 073, 29 Oct 2001. Submitted to 14th Canadian Conference on Computational Geometry, Lethbridge, Alberta, August 2002. [Postscript available. See also the figure below.]

J. O'Rourke, Octavia Petrovici ('01), "Narrowing Light Rays with Mirrors" in Proc. of the 13th Canadian Conference on Computational Geometry, Waterloo, Ontario, August 2001, pp. 137-140. [Postscript and code available.]

J. O'Rourke, Irena Pashchenko ('01), Geetika Tewari ('02), "Partitioning Orthogonal Polygons into Fat Rectangles" in Proc. of the 13th Canadian Conference on Computational Geometry, Waterloo, Ontario, August 2001, pp. 133-136. [Postscript available.]

Biliana Kaneva ('00) and J.O'Rourke, "An Implementation of Chen & Han's Shortest Paths Algorithm," Proceedings of the 12th Canadian Conference on Computational Geometry, August 2000. [Postscript available.] See the figure and link below.

J. O'Rourke and The Smith Problem Solving Group (including Beenish Chaudry ('02), Sorina Chircu ('00), Elizabeth Churchill ('00), Sasha Fedorova ('99), Biliana Kaneva ('00), Haley Miller ('00), Irena Pashchenko ('01), Geetika Tewari ('02), Elif Tosun ('02).) "PushPush is NP-hard in 3D." Smith Technical Report 064, Nov. 1999. [Postscript available.]

Roxana Cocan ('99) and J.O'Rourke, "Polygonal chains cannot lock in 4D," Computational Geometry Theory and Applcations, to appear, 2002.
Abstract in Proceedings of the 11th Canadian Conference on Computational Geometry, August, 1999, pp. 5-8. [Postscript available.]

E. Demaine, M. Demaine, A. Lubiw, J. O'Rourke and Irena Pashchenko ('01), "Metamorphosis of the Cube," 8th Annual ACM Video Review of Computational Geometry: video plus paper in the Proceedings of the ACM Symposium on Computational Geometry, June 1999, pp. 409-410.
For an 8MB MPEG downloadable version of the video, see Erik Demaine's Metamorphosis page.

J. O'Rourke and Irena Pashchenko ('01), "Zero-Parity Stabbing Information," Japan Conference on Discrete and Computational Geometry, Tokyo, Dec. 1998, pp. 93-97. [Postscript available.] See the figure below.

Estivill-Castro, V., O'Rourke, J., Urrutia, J., Dianna Xu ('96), "Illumination of Polygons with Vertex Lights," Info. Proc. Lett. 56 (1995) 9-13. [Postscript available.]

Carole Gitlin ('93), J. O'Rourke, and Vinita Subramanian ('91). "On reconstruction of polyhedra from slices," Int. J. Comput. Geom. & Appl., 6(1) 1996: 103-112. [Postscript available.] See the figures below.

O'Rourke, J., Jennifer Rippel ('92) (1994). "Two segment classes with Hamiltonian visibility graphs," Computational Geometry: Theory and Applications, Vol. 4, 209-218.

J. O'Rourke, Jennifer Rippel ('92), ``Segment visibility graphs: several results,'' Fourth Canadian Conference on Computational Geometry, August 1992, pp. 35-38.

Anu Dhagat ('92), J. O'Rourke (1992). "Motion planning amidst movable square blocks," Proceeding of Fourth Canadian Conference on Computational Geometry, 188-191.

Susan Jones(Dorward) ('90), and J. O'Rourke. "A note on moving a chair through a doorway," Algorithms Review, Vol. 1, No. 3, 139-149, 1990.

In Artificial Intelligence

Megan Bredeweg ('02) and J. O'Rourke, Review of Gregory Mulhauser, Mind out of Matter: Topics in the Physical Foundations of Consciousness and Cognition, Kluwer Academic, 1998; Intelligence, Vol. 11, No. 1, pp.53-55, Spring 2000.

Marina Brown ('00) and J. O'Rourke, Review of Bringsjord, What Robots Can and Can't Be (Kluwer Academic, 1992), "Agnosticism About the Arbitrary Realization Argument." Psycoloquy 5(83) 30 December 1994.
ftp psyc.94.5.83.robot-consciousness.3.brown.
"Agnosticism Revisited: Reply to Bringsjord on Robot-Consciousness" (rebuttal) Psycoloquy, 6(21) 3 July 1995.
ftp psycoloquy.95.6.21.robot-consciousness.14.brown.

Amy Hoff ('96), Review of Natarajan, Machine Learning, in SIGART Bulletin, Vol. 4, No. 4, Oct. 1993, pp. 14-15.

Research Gallery

The 23 Foldings of the Latin Cross. Work with Caitlin Brady '03, Sasha Berkoff '05, Sonya Nikolova '03.
See our full poster for more details.
A Gluing Graph on 77 vertices. Work with Beenish Chaudry '02.
GG77

Nonorthogonal Polyhedra Built from Rectangles. Work with Melody Donoso '04. [See our paper.]
The polyhedron below is built entirely from rectangles, but none of its dihedral angles are multiples of pi/2, i.e., it is not an orthogonal polyhedron. This answers a question posed by Biedl, Lubiw, and Sun. It was discovered independently by Martin Demaine. The polyhedron shown has genus seven. In contrast, we proved that every polyhedron of genus zero or one built from rectangles is an orthogonal polyhedron.

A generalization of Cauchy's "Arm Lemma" [O'R00]. The image below shows the reachability region for robot arm (polygonal chain) whose initial position forms a convex polygon, and which is permitted to move each joint within the turn angle range indicated in green. The reachability region must lie outside the blue "forbidden shoulder circle." See the Cauchy applet implemented by Veronica Morales '01 for further details.


Shortest paths on the surface of a convex polyhedron. Work with Biliana Kaneva '00 and Diana Xu '96. The figure below is output from an implementation of Chen & Han's shortest path algorithm, developed by Biliana Kaneva, following an earlier implementation by Diana Xu. It shows the shortest paths from one source point to every vertex on a polytope whose 100 vertices are on a sphere. See our Shortest Paths web pages for more figures and further details.


Dissection of one shape A into two pieces and reassembling into another shape B. Work in progress with Erik Demaine, Marty Demaine, and Irena Pashchenko '01.


A chain of five unit-length cylindrical links, which is "locked." No chain of five unit-length segment links can lock, as proven by Cantarella and Johnston. Work with Sorina Chircu '00.

Reconstruction of the internal and external visibility graphs of a polygon from stabbing information. Work with Irena Pashchenko. Stabbing information records the number of polygon edges crossed by each line determined by two vertices. We proved that the zero-parity information is insufficient to determine the visibility graphs, and identified a particular structural obstruction to reconstruction. See paper above. The example below, although quite complex, avoids the obstruction, and so its visibility graphs are determined and found by our algorithm.


The left figure below shows two polygons lying in parallel planes. The right figure shows a simple polyhedron connecting those polygons. (Figure produced by algorithms implemented by Wendy Welsh and Anna Lysyanskya.) Slicing this polyhedron with z=h planes produces a morphing between the two polygons, which can be easily animated.

Two polygons that cannot be connected by a polyhedron (top view). From the Gitlin, O'R, Subramanian paper cited above. To the right is a much nicer image of the same figure, created by Jeff Erickson, and used here by his permission.
[Unmateable Polygons]

The last two figures about concern the following problem that arises in medical imaging.
From a CAT or MRI scan, slices through a three-dimensional object are obtained, perhaps a brain tumor. From these slices the object must be "reconstructed." The basic step of this reconstruction is connecting two polygons lying in parallel planes. The connection is effected by finding a collection of triangles that span the two planes, have their corners at vertices of the polygons, and fit together seamlessly to form a closed polyhedron. This basic problem of reconstructing a polyhedron from two parallel polygonal slices has been heavily studied due to its importance, but no completely satisfactory algorithm has been found. I have worked on this problem with a succession of Smith honors students.

One of our achievements is contained in a journal article listed below: we establish the surprising result that there exist pairs of polygons that cannot be connected by triangles to form a simple polyhedron. Such polygons are fundamentally incompatible, and cannot be connected by any algorithm. With one thesis student (Vinita Subramanian) we developed a complicated proof of this result. With a second student (Carole Gitlin) we simplified the proof and verified it with an exhaustive computer search. Two other students (Wendy Welsh and Anna Lysyanskya) developed heuristic algorithms that will find a connection if one exists, and incrementally improve it to be "natural." (See images below.) Another student (Amy Josefczyk) explored extending the algorithm to four dimensions.



Last Update: