On the average length of Delaunay triangulations
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)].
- scientific article; zbMATH DE number 176773
- THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
- Size analysis of nearly regular Delaunay triangulations
- Complexity of the Delaunay triangulation of points on polyhedral surfaces
- Almost regular Delaunay-triangulations
- On the number of higher order Delaunay triangulations
- On the Number of Higher Order Delaunay Triangulations
- A tight bound for the Delaunay triangulation of points on a polyhedron
- On the stretch factor of Delaunay triangulations of points in convex position
- A Lower Bound for the Expected Travel Among m Random Points
- A note on Delaunay and optimal triangulations
- scientific article; zbMATH DE number 3612276 (Why is no real title available?)
- scientific article; zbMATH DE number 3633698 (Why is no real title available?)
- Multidimensional divide-and-conquer
- Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
- On the homogeneous planar Poisson point process
- Stochastic Point Processes: Limit Theorems
- Two algorithms for constructing a Delaunay triangulation
- Computing relative neighbourhood graphs in the plane
- Asymptotics for the length of a minimal triangulation on a random sample
- Size analysis of nearly regular Delaunay triangulations
- Fast greedy triangulation algorithms.
- Minimum Average Distance Triangulations
- THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
- A New Heuristic for Minimum Weight Triangulation
- scientific article; zbMATH DE number 176773 (Why is no real title available?)
- On smallest triangles
- Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}
- On the number of higher order Delaunay triangulations
- Delaunay graphs are almost as good as complete graphs
- On exclusion regions for optimal triangulations
- Greedy triangulation can be efficiently implemented in the average case
- Expected length of the Voronoi path in a high dimensional Poisson-Delaunay triangulation
- Toughness and Delaunay triangulations
This page was built for publication: On the average length of Delaunay triangulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062440)
