A tight bound for the Delaunay triangulation of points on a polyhedron (Q443906)

A not necessarily convex or connected \(p\)-dimensional polyhedron \(P\) in \(d\)-dimensional Euclidean space is considered. Let \(S\) denote a point set representing a sparse \(\varepsilon\)-sampling covering every face of \(P\). The complexity of the Delaunay triangulation of \(S\) is analyzed for \(\varepsilon \to 0\). It is shown that the number of all simplices of all dimensions is \(O\left(n^{\frac{d-k+1}{p}}\right)\) where \(k=\left\lceil\frac{d+1}{p+1}\right\rceil\). In the worst case, the bound is tight. This is shown by way of constructing a specific polyhedron \(P\). The proof of the upper bound is based on mapping Delaunay simplices to the points of a generalized medial axis, defined by annuli tangential to the boundary of \(P\), and using a packing argument on a bounded subset of this annular medial axis.