THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
- 1 March 1991
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 01 (01) , 79-91
- https://doi.org/10.1142/s0218195991000074
Abstract
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 n1/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 Θ( 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.Keywords
This publication has 0 references indexed in Scilit: