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.
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.)
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 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 (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 is currently pursuing a Ph.D. in Applied Mathematics at MIT.
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.
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 (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(n42). Her work was summarized in the paper below. Geetika obtained her Ph.D. in Computer Graphics from Harvard University in 2007.
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 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.
"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.
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.
"Agnosticism Revisited: Reply to Bringsjord on Robot-Consciousness" (rebuttal) Psycoloquy, 6(21) 3 July 1995.
Amy Hoff ('96), Review of Natarajan, Machine Learning, in SIGART Bulletin, Vol. 4, No. 4, Oct. 1993, pp. 14-15.
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.