DocumentCode :
2886453
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
fYear :
1991
fDate :
16-17 Jun 1991
Firstpage :
644
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 1991. Conference Proceedings, China., 1991 International Conference on
Conference_Location :
Shenzhen
Type :
conf
DOI :
10.1109/CICCAS.1991.184439
Filename :
184439
Link To Document :
بازگشت