This figure shows two polygons that cannot be connected by triangles to form a simple polyhedron unless extra vertices are added. (Joining parallel polygons into simple polyhedra is a basic step in the reconstruction of 3-dimensional objects from parallel slices, a problem that arises in medical imaging.) The history of this surprising result can be found on Joe O'Rourke's research page.
Technical details can be found in "On Constructing Polyhedra from Parallel Slices" by Carole Gitlin, Joe O'Rourke, and Vinita Subramanian, International Journal of Computational Geometry & Applications, 6(1) 1996: 103-112.
I am seriously considering changing the title image to this picture from the children's book Monkey Business by J.otto Seibold and Vivian Walsh (Viking, 1995), but only if I can get permission from the authors. (In the meantime, please don't make copies of this image!) Monkey Business is a story about an space-faring monkey who runs a polytope factory with his supercomputer, and a bug named Penelope that finds a new home inside their one millionth polytope. No, really.
In the picture, Space Monkey is mentally constructing the convex hull of a set of points, which were taken from astronomical data gathered two pages earlier, by building the upper and lower hulls separately and then joining them along their common silhouette. The supercomputer is reading Space Monkey's mind and figuring out the implementation details. I want a computer like that.
Computational Geometry Pages
by Jeff Erickson
Last update: 04 Dec 97
Your feedback is always welcome.