A numerical stable algorithm for constructing constrained Delaunay triangulation and application to multichip module layout

摘要

Presents some characteristics of constrained Delaunay triangulation and introduces a numerically stable algorithm for incrementally constructing constrained Delaunay triangulation. This algorithm produces constrained Delaunay triangulation at each step. It builds Delaunay triangulation in O(N/sup 2/) time in the worst case. However, its average case performance is O(NlogN). Since the algorithm mainly uses the circle criterion, it arises the precision problem, such as whether a point is inside, outside or exactly on a circle. The authors present a method to conceptually avoid the numerical errors. The experimental results are shown in this paper.