On the average length of Delaunay triangulations (Q1062440)

Let P be a finite set of points in the plane. The authors consider the length of triangulations of P, i.e. of a maximal subset of all straight- line segments whose endpoints are in P, intersecting at the points of P only. The length is the total length of all straight-line segments in the triangulation. The Delaunay triangulation is defined by the property that the circumcircle of any triangle in the triangulation does not contain any point of P in its interior. This triangulation is the dual of the so- called Voronoi diagram of P. - It is well known that the Delaunay triangulation is in general not of minimal length. Let DT(P) denote the length of the Delaunay triangulation and MT(P) denote that of a minimal triangulation. Then it has been proved before that there are sequences of sets \(P=P_ n\), consisting of n points each, such that \(MP(P_ n)=DT(P_ n)\cdot O((\log n)/n).\) In strengthening a result due to \textit{A. Lingas} [Dissertation, Linköping University, Sweden (1983)] the authors prove in this paper that in average \(DT(P_ n)=O(MT(P_ n))\) for all sequences \(P_ n\) which are distributed uniformly in the unit square. More precisely, if the n points of \(P_ n\) are put into the unit square by a homogeneous planar Poisson distribution, then one gets for the corresponding expectation values the inequality \(E(DT(P_ n))\leq (64/9\pi)E(MT(P_ n))\). The proof consists mainly in an efficient combination of two earlier results of \textit{E. S. Marks} [Ann. Math. Stat. 19, 419-422 (1948; Zbl 0031.36702)] and of \textit{R. E. Miles} [Math. Biosci. 6, 85-127 (1970; Zbl 0196.194)].