Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
复制标题
低维多面体上点的 Delaunay 三角剖分的复杂性
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
O. Devillers
中科院分区：
文献类型：
--
作者：
N. Amenta;D. Attali;O. Devillers
证明了d维空间中几乎均匀分布在p维多面体(不一定凸)上的一组点的Delaunay三角剖分是O(n<sup>(d-1)<p</sup>)。对于所有2≤<p</sup>≤</sup>d</sup>-1，这比众所周知的最坏情况界<0</sup>(<n>⌈d/2⌉</sup>)有所改善。
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension <i>p</i> in <i>d</i>-dimensional space is <i>O</i>(<i>n</i><sup>(d-1)/<i>p</i></sup>). For all 2 ≤ <i>p</i> ≤ <i>d</i> - 1, this improves on the well-known worst-case bound of <i>O</i>(<i>n</i><sup>⌈d/2⌉</sup>).