Inflating 2D Triangulations to 3D Convex Polyhedra Ben Marlin 
  Welcome | Guibas' Conjecture | Realizability | Algorithms | Applet | Counter Example | Sources



This project is based on a conjecture made during the proceedings of the First Canadian Conference on Computational Geometry at McGill University in 1989 by Prof. Leonidas J. Guibas of Stanford University. A counter example to this conjecture was given in a paper published in 1995 by Prof. Boris Dekster of Mt. Allison University. According to anecdotal evidence, Guibas supposedly knew of a counter example before Dekster's paper was published.

In this project we will look at Guibas' conjecture and the intuitions behind it. We will then attempt to identify several different classes of examples for which the conjecture holds, including the single class given by Dekster. An interactive Java applet for constructing such examples is provided to give the reader some intuition about the objects in question. Finally, a counter example to Guibas' conjecture will be given and shown to be correct.

Since the subject matter of this project deals mainly with objects in three dimensions it quickly becomes obvious that two dimensional images do not suffice when it comes to examples. To help alleviate the difficulties involved with conceptualizing objects in three dimensions, all figures contained in this project are 3D models rendered using a simple Java applet. By clicking on any of the figures and dragging the mouse, you can spin the corresponding model around to get a better sense of it's structure. An example of this applet is provided at the right. You should take a minute to familiarize yourself with how the applet works before proceeding with the rest of the sections.

Technical Requirements:

Any web browser will work for viewing the text of this project, but to get the full effect you should have a browser that supports the Java 2 plug in. This should include any version of Netscape Navigator above 4.0 for both MS Windows and Linux, as well as most versions of Internet Explorer above version 5.0. If you do not see an applet on this page, your browser does not support Java 2, or you need to enable Java in your browser's preferences section.

McGill University School of Computer Science
Ben Marlin - 2001