Book Description

Abstract: "The Voronoi diagram is a partition of a set S of N points in a plane, such that each region is the locus of the points (x, y) closer to a point of S than to any other point of S. If no four points are co-circular, the Delaunay triangulation is the straight-line dual of the Voronoi diagram. The triangulation may be constrained, that is, a set of straight-line segments may be prespecified. This thesis presents some characteristics of constrained Delaunay triangulation and introduces a set of numerically stable algorithms for incremently constructing and updating constrained Delaunay triangulation. The dynamic constrained Delaunay triangulation algorithms have been implemented in a layout system for multichip modules. It has been used as the underlying data representation for rubber-band sketch, a topological routing for one layer. We have proved the O(n log n) expected running time for the Delaunay triangulation algorithm."