THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION

被引：26

作者：

Bern, Marshall ^{[1
]}

Eppstein, David ^{[2
]}

Yao, Frances ^{[1
]}

机构：

[1] Xerox Palo Alto Res Ctr, Palo Alto, CA 94304 USA

[2] Univ Calif Irvine, Dept Informat & Comp Sci, Irvine, CA 92717 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1991年 / 1卷 / 01期

关键词：

Computational geometry; Delaunay triangulation; probabilistic analysis;

D O I：

10.1142/S0218195991000074

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：79 / 91

页数：13

共 15 条

[1]

[Anonymous], 1987, EATCS MONOGRAPHS THE

[2]

Bern M., 1990, J COMPUT SYST SCI, V48, P231

[3]

CRAIN IK, 1972, SEARCH, V3, P220

[4] THE EXPECTED LENGTH OF THE LONGEST PROBE SEQUENCE FOR BUCKET SEARCHING WHEN THE DISTRIBUTION IS NOT UNIFORM [J].