Title :
A numerical stable algorithm for constructing constrained Delaunay triangulation and application to multichip module layout
Author :
Lu, Yizhi ; Dai, Wayne Wei-Ming
Author_Institution :
Comput. Eng. Board of Studies, California Univ., Santa Cruz, CA, USA
Abstract :
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(N2) 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
Keywords :
circuit layout CAD; hybrid integrated circuits; characteristics; circle criterion; constrained Delaunay triangulation; experimental results; incremental construction; multichip module layout; numerical stable algorithm; precision problem; Application software; Error correction; Multichip modules;
Conference_Titel :
Circuits and Systems, 1991. Conference Proceedings, China., 1991 International Conference on
Conference_Location :
Shenzhen
DOI :
10.1109/CICCAS.1991.184439