DYNAMIC CONSTRAINED DELAUNEY TRIANGULATION AND APPLICATION TO MULTICHIP MODULE LAYOUT (M.S. Thesis)

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.