Nice Point Sets Can Have Nasty Delaunay Triangulations
Nice Point Sets Can Have Nasty Delaunay Triangulations
复制标题
好的点集可能有令人讨厌的 Delaunay 三角剖分
DOI：
10.1145/378583.378636
复制
发表时间：
2001
影响因子：
0.8
通讯作者：
Jeff Erickson
中科院分区：
文献类型：
--
作者：
Jeff Erickson
抽象的。我们考虑在一定的实际几何约束下，在R3中的点集的Delaunay三角剖分的复杂性。一组点的散布是最长和最短成对距离之间的比率。我们证明了在最坏的情况下，R3中n个点的Delaunay三角剖分的复杂度为Ω（min{ Δ3，nΔ，n2 }）和O（min{ Δ4，n2 }）.对于$\Delta = \Theta（\sqrt{n}）$的情况，我们的下限构造由具有恒定高度和半径的直圆柱体的网格状样本组成。我们还构造了一个家庭的光滑连接的表面，使得任何好的点样本的Delaunay三角剖分有近二次的复杂性。
Abstract. We consider the complexity of Delaunay triangulations of sets of points in R3 under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in R3 with spread Δ has complexity Ω(min{ Δ3, nΔ, n2 }) and O(min{ Δ4, n2 }). For the case $\Delta = \Theta(\sqrt{n})$ , our lower bound construction consists of a grid-like sample of a right circular cylinder with constant height and radius. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.