2 ALGORITHMS FOR CONSTRUCTING A DELAUNAY TRIANGULATION
2 ALGORITHMS FOR CONSTRUCTING A DELAUNAY TRIANGULATION
复制标题
DOI：
10.1007/bf00977785
复制
发表时间：
1980-01-01
期刊：
影响因子：
--
通讯作者：
SCHACHTER, BJ
中科院分区：
文献类型：
--
作者：
LEE, DT;SCHACHTER, BJ
本文对Delaunay三角网进行了统一的讨论。它的几何性质进行了审查和几个应用进行了讨论。本文提出了两种在平面N点集上构造三角网的算法。第一种算法使用分治法。该算法的时间复杂度为O（NlogN），是渐近最优的。第二个算法是迭代的，在最坏的情况下需要O（N2）时间。然而，它的平均情况下的性能是可比的第一个算法。
This paper provides a unified discussion of the Delaunay triangulation. Its geometric properties are reviewed and several applications are discussed. Two algorithms are presented for constructing the triangulation over a planar set ofNpoints. The first algorithm uses a divide-and-conquer approach. It runs inO(NlogN) time, which is asymptotically optimal. The second algorithm is iterative and requiresO(N2) time in the worst case. However, its average case performance is comparable to that of the first algorithm.