Complexity of the Delaunay triangulation of points on polyhedral surfaces (Q1434252)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity of the Delaunay triangulation of points on polyhedral surfaces |
scientific article |
Statements
Complexity of the Delaunay triangulation of points on polyhedral surfaces (English)
0 references
7 July 2004
0 references
This paper studies the expected complexity of the Delaunay triangulations of points distributed on the boundary of a given polyhedron in 3-space. It is shown that under certain sampling conditions the expected complexity is \(O(n^{1.8})\) for general polyhedral surfaces and \(O(n\sqrt{n})\) for convex polyhedral surfaces. This differs remarkably from the known worst-case complexity of \(O(n^2)\), and the expected linear complexity for uniform distribution on a cube or ball. The result is based on a result that shows the medial axis is well approximated by a subset of the Voronoi vertices of the sample points.
0 references
Delaunay triangulation
0 references
polyhedral surfaces
0 references
complexity
0 references