A tight bound for the Delaunay triangulation of points on a polyhedron
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.
- Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
- Complexity of the Delaunay triangulation of points on polyhedral surfaces
- A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces
- Dense point sets have sparse Delaunay triangulations or ``\dots but not too nasty
- Complexity of the Delaunay triangulation of points on surfaces the smooth case (extended abstract)
- A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces
- Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
- Complexity of the Delaunay triangulation of points on surfaces the smooth case (extended abstract)
- scientific article; zbMATH DE number 192849 (Why is no real title available?)
- scientific article; zbMATH DE number 5239226 (Why is no real title available?)
- Nice point sets can have nasty Delaunay triangulations
- On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
- The maximum numbers of faces of a convex polytope
- The probabilistic complexity of the Voronoi diagram of points on a polyhedron
- The Probability That a Numerical Analysis Problem is Difficult
- On the average length of Delaunay triangulations
- Complexity of the Delaunay triangulation of points on polyhedral surfaces
- Dense point sets have sparse Delaunay triangulations or ``\dots but not too nasty
- A monotonicity property for weighted Delaunay triangulations
- A variational principle for weighted Delaunay triangulations and hyperideal polyhedra
- Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
- THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
- DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
- scientific article; zbMATH DE number 2080989 (Why is no real title available?)
- scientific article; zbMATH DE number 2119653 (Why is no real title available?)
- On the size of higher-dimensional triangulations
- Nice point sets can have nasty Delaunay triangulations
- scientific article; zbMATH DE number 5242321 (Why is no real title available?)
- A short proof of the toughness of Delaunay triangulations
- On the stretch factor of Delaunay triangulations of points in convex position
- An upper bound for conforming Delaunay triangulations
- Bounded-degree polyhedronization of point sets
- A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces
- RDELA -- a Delaunay-triangulation-based, location and covariance estimator with high breakdown point
- A weak characterisation of the Delaunay triangulation
This page was built for publication: A tight bound for the Delaunay triangulation of points on a polyhedron
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q443906)
