Delaunay Triangulations of Imprecise Points in Linear Time after Preprocessing

被引：4

作者：

Loffler, Maarten ^{[1
]}

Snoeyink, Jack ^{[1
]}

机构：

[1] Univ Utrecht, Dept Informat & Comp Sci, Utrecht, Netherlands

来源：

PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SGG'08) | 2008年

关键词：

Data imprecision; Delaunay triangulation; Gabriel graph; Minimum spanning tree;

D O I：

10.1145/1377676.1377727

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An assumption of nearly all algorithms in computational geometry is that the input points are given precisely, so it is interesting to ask what is the value of imprecise information about points. We show how to preprocess a set of n disjoint unit disks in the plane in O(n log n) time so that if one point per disk is specified with precise coordinates, the Delaunay triangulation can be computed in linear time. From the Delaunay, one can obtain the Gabriel graph and a Euclidean minimum spanning tree; it is interesting to note the roles that these two structures play in our algorithm to quickly compute the Delaunay.

引用

页码：298 / 304

页数：7

共 30 条

[21] LOFFLER M, 2008, ALGORITHMIC IN PRESS
[22] MEHLHORN K, 2000, LEDA PLATFORM COMBIN
[23] SEIDEL R, 1985, COMPUTATIONAL GEOMET, P319
[24] Delaunay refinement algorithms for triangular mesh generation
Shewchuk, JR
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2002, 22 (1-3): : 21 - 74
[25] SPECHT E, 2007, BEST KNOWN PACKINGS
[26] CONSTRUCTION OF THE VORONOI DIAGRAM FOR ONE MILLION GENERATORS IN SINGLE-PRECISION ARITHMETIC
SUGIHARA, K
IRI, M
[J]. PROCEEDINGS OF THE IEEE, 1992, 80 (09) : 1471 - 1484
[27] SUGIHARA K, 1989, APPL MATH LETT, V2, P203
[28] VANKREVELD M, 2007, LNCS, V4619, P447
[29] WELLER F, 1997, P 9 CAN C COMP GEOM, P251
[30] Yap C.K., 2004, Handbook of Discrete and Computational Geometry, V2nd, P927

← 1 2 3 →