Characterizing and Efficiently Computing Quadrangulations of Planar Point Sets

for course 308-507A Computational Geometry Prof: Godfried Toussaint McGill University, Autumn 1997   prepared by Martin Blais

This is a presentation web page for the following paper:

A Postscript version of this paper is available on the web at Godfried Toussaint's home page.

It is shown here how to efficiently quadrangulate a set of points in the plane.  An explanation of the algorithm is depicted in these web pages, and a Java applet is provided which allows you to observe the algorithm and results on user-specified input points.

Main Page | Abstract | Introduction | Algorithm | Results | Applet | References | Comments