12/01/1992 09:00 AM
Computer Science
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 Delauney triangulation algorithm. Keywords: Voronoi diagram, Delaunay triangulation, constrained Delauney triangulation, layout, multichip module, topological routing. Notes: M.S. Thesis
