On the average length of Delaunay triangulations
type: Item
instance of: scholarly article
title: On the average length of Delaunay triangulations
zbMATH Open document ID: 0572.65099
DOI: 10.1007/BF02136025
published in: BIT
publication date: 1984-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 65N50
Mathematics Subject Classification ID: 65N30
zbMATH DE Number: 3913623
zbMATH Keywords: Delaunay triangulation
zbMATH Keywords: Voronoi diagram
zbMATH Keywords: minimal triangulation
zbMATH Keywords: Poisson distribution
author: R. C. Chang
author: R. C. T. Lee
MaRDI profile type: Publication
cites work: Multidimensional divide-and-conquer
cites work: Stochastic Point Processes: Limit Theorems
cites work: A note on Delaunay and optimal triangulations
cites work: Q4194442
cites work: Two algorithms for constructing a Delaunay triangulation
cites work: Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
cites work: A Lower Bound for the Expected Travel Among $m$ Random Points
cites work: On the homogeneous planar Poisson point process
cites work: Q4176809
Recommended article: Q4036603
Recommended article: THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
Recommended article: Size analysis of nearly regular Delaunay triangulations
Recommended article: Complexity of the Delaunay triangulation of points on polyhedral surfaces
Recommended article: Almost regular Delaunay-triangulations
Recommended article: On the number of higher order Delaunay triangulations
Recommended article: On the Number of Higher Order Delaunay Triangulations
Recommended article: A tight bound for the Delaunay triangulation of points on a polyhedron
Recommended article: On the stretch factor of Delaunay triangulations of points in convex position
description: scientific article; zbMATH DE number 3913623