On the number of higher order Delaunay triangulations (Q551184)

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.