A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron

作者：Amenta Nina^*; Attali Dominique; Devillers Olivier

来源：Discrete & Computational Geometry, 2012, 48(1): 19-38.

DOI：10.1007/s00454-012-9415-7

• Delaunay triangulation
• Complexity
• Upper bound
• High dimension
• Polyhedron
• Annular medial axis
• Sampling

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a -dimensional polyhedron (not necessarily convex) in -dimensional Euclidean space is , where . This bound is tight in the worst case and improves on the prior upper bound for most values of .

• 出版日期2012-7
• 单位INRIA