Joseph O'Rourke: Research Summary

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 co-authored research monograph Geometric Folding Algorithms, and two books at the high-school level, How To Fold It and Pop-Up Geometry. 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 co-authored textbook. See my (partial) list of papers here. My latest work is on Reshaping Convex Polyhedra.

Here is one of my 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.)

YouJeen Ha (2020): "Causation in Machine Learning"

The challenge of inferring causality (vs. correlation) from data via Machine Learning.

Zoe Riell (2019): "Computing Principal Lines of Curvature on Polyhedra"

Principle lines of curvature are defined for smooth surfaces. There is some challenge to computing approximations on a polyhedral surface.

Zainab Syeda Rizvi (2018): "Computing maximum volume polyhedral wrappings"
Implementing Igor Pak's proof that any convex polyhedron's volume can be increased via an isometric deformation.
Betsy Mackenzie (2013): "Physical Properties of Polyhedra"
Betsy computed the center of gravity and moment of inertia tensor of an arbitrary polyhedron, leading to animations of polyhedra tumbling weightless in space according to Euler's equations of motion.
Angela Tosca (2011): "The Limits of Computation under the Turing Machine Model"
Angela explored both the theoretical boundary of Turing-computability, specifically hypercomputation, as well as the physical realizability of a variety of models of computation. Then within the Turing-computable, she explored the boundary between the feasible and the infeasible computations, with special focus on quantum computation, and the implications for machine learning.
Hannah Bier (2009): "Automated analysis of DNA electrophoresis gel photos."
Hannah developed software to take as input a DNA gel photo, and isolate and analyze the lanes and bands to determine the molecular weight of the DNA fragments and their length in amino acid base pairs. Hannah is pursuing a Ph.D. in Bioinformatics at Dartmouth University.
Nadia Benbernou (2007): "Fixed-angle polygonal chains: Locked chains and the maximum span"
Nadia (a math major) explored the geometry of fixed-angle polygonal chains as a model of protein backbones. One notable result in her thesis is that a fixed-angle chain of unit-length links is necessarily planar when maximally stretched out. Her work is described in the paper below. Nadia was awarded the Ph.D. in Applied Mathematics from MIT in 2012.
Suzanne Gallagher (2006): "Coloring objects built from bricks"
Suzanne (double Math/CS major) wrote her thesis on coloring objects built from bricks glued face-to-face, coloring so that no two adjacent bricks have the same color. One nice theorem she proved is that any genus-zero (= no holes) object built from rectangular bricks is 2-colorable. We raised some novel questions that remain unsolved today. Her work was summarized in the paper below. Suzanne is finishing her Ph.D. in Graph Algorithms at the University of Colorado.
Beenish Chaudry (2003): "Double gluing graphs and the discrete sliding conjecture"
Work with another student, Irena Pashchenko, suggested that a certain folding algorithm, which had only been proven to work in exponential time, might in fact run in polynomial time, if the "discrete sliding conjecture" were true. She settled it in a special case. The conjecture remains open today. In pursuing the conjecture she and I invented "double gluing graphs," which are sometimes quite beautiful. Beenish is pursuing a Ph.D. in Quantum Computing at Indiana University.
Geetika Tewari (2002): "Partitioning orthogonal polygons into fat rectangles"
Geetika (and Irena Pashchenko before her) worked on a partitioning problem that arose from masking VLSI chips at IBM. The problem is to cover a chip shape with "fat rectangles." The problem is surprisingly intricate, leading to an algorithm we could only upperbound by O(n⁴²). Her work was summarized in the paper below. Geetika obtained her Ph.D. in Computer Graphics from Harvard University in 2007.
Octavia Petrovici (2001): "Trapping light rays with mirrors"
Octavia studied what happens when light rays repeatedly bounce off a collection of either flat or circular mirrors. We wrote a paper that posed nine conjectures, only one of which (I believe) is settled today. One in particular has been the focus of considerable attention. Octavia is a senior design programmer at Microsoft, developing Windows Vista and Version 7, among other projects.
Biliana Kaneva (2000): "An implementation of Chen & Han's shortest paths algorithm"
Biliana wrote the first robust software to compute all the shortest paths on a polyhedral manifold. Her work was summarized in the paper below, and is frequently cited. Biliana worked at Microsoft for several years, and is now pursuing a Ph.D. in Computer Vision at MIT.

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

J. O'Rourke and Emmely Rogers. "Threadable Curves." 30th Canad. Conf. Comput. Geom., Jun 2018. pp. 328-333. Full version: arXiv 1801.08003 [cs.CG].

Giovanna Diaz and J. O'Rourke. "Hypercube Unfoldings that Tile R³ and R²." arXiv:1512.02086 [cs.CG]. Dec 2015.

Stephanie Jakus and J. O'Rourke. "From Pop-Up Cards to Coffee-Cup Caustics: The Knight's Visor." arXiv:1206.1312v1 [cs.CG]. Jun 2012.

Yonit Bousany, Mary Leah Karker, J. O'Rourke, Leona Sparaco. "Sweeping Minimum Perimeter Enclosing Parallelograms: Optimal Crumb Cleanup." Canadian Conference on Computational Geometry, pp. 167-170, Winnipeg, Aug 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.

J. 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), J. 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.

J. 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 J. 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.

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: