On the number of higher order Delaunay triangulations (Q551184)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the number of higher order Delaunay triangulations |
scientific article |
Statements
On the number of higher order Delaunay triangulations (English)
0 references
14 July 2011
0 references
An order-\(k\) Delaunay triangulation is a Delaunay triangulation of a set of points \(\mathcal P\) in the Euclidean plane in which the circumcircle of each triangle of the triangulation bounds at most \(k\) points in \(\mathcal P\). It is proved that for any integers \(n \geq 6\) and \(k\) such that \(k \leq \lfloor n/3 \rfloor -1\), there exist \(n\) points in general position in the plane which allow only one order-\(k\) Delaunay triangulation. It is also proved that any set of \(n\) points in general position has at most \(2^{n-3}\) order-\(1\) Delaunay triangulations and that this bound is tight. The main result is that given a random set of \(n\) points in the unit square (uniformly distributed), the expected number of order-\(1\) Delaunay triangulations is at least \(2^{\rho_1n(1+o(1))}\), where \(\rho_1 \approx 0.525785\), and the expected number of order-\(k\) Delaunay triangulations is at least \(2^{\rho_kn(1+o(1))}\), for a fixed \(k \geq 2\), where \(\rho_k\) can be calculated numerically.
0 references
computational geometry
0 references
Delaunay triangulation
0 references
higher order Delaunay triangulation
0 references
random geometric graph
0 references
random point set
0 references