×

The expected extremes in a Delaunay triangulation. (English) Zbl 0724.68084

Summary: We give an expected-case analysis of Delaunay triangulations. To avoid edge effects we consider a unit-intensity Poisson process in Euclidean d- space, and then limit attention to the portion of the triangulation within a cube of side \(n^{1/d}\). For d-equal to two, we calculate the expected maximum edge length, the expected minimum and maximum angles, and the average aspect ratio of a triangle. We also show that in any fixed dimension the expected maximum vertex degree is \(\theta\) (log n/log log n). Altogether our results provide some measure of the suitability of the Delaunay triangulation for certain applications, such as interpolation and mesh generation.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI