A replacement for Voronoi diagrams of near linear size

被引：73

作者：

Har-Peled, S ^{[1
]}

机构：

[1] Univ Illinois, Dept Comp Sci, Urbana, IL 61801 USA

来源：

42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2001年

关键词：

D O I：

10.1109/SFCS.2001.959884

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

For a set P of n points in R-d, we define a new type of space decomposition. The new diagram provides an epsilon -approximation to the distance function associated with the Voronoi diagram of P, while being of near linear size, for d greater than or equal to 2. This contrasts with the standard Voronoi diagram that has Omega (n ([d/2])) complexity in the worst case.

引用

页码：94 / 103

页数：10

共 18 条

[11] CONVEX PARTITIONS OF POLYHEDRA - A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM
CHAZELLE, B
[J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (03) : 488 - 507
[12] Clarkson K. L., 1994, Proceedings of the Tenth Annual Symposium on Computational Geometry, P160, DOI 10.1145/177424.177609
[13] Erickson J., 2001, P 17 ANN ACM S COMP, P96
[14] DATA-STRUCTURES FOR ONLINE UPDATING OF MINIMUM SPANNING-TREES, WITH APPLICATIONS
FREDERICKSON, GN
[J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (04) : 781 - 798
[15] HARPELED S, 2001, IN PRESS P 42 ANN IE
[16] Hart, 2006, PATTERN CLASSIFICATI
[17] Indyk P., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P604, DOI 10.1145/276698.276876
[18] Kushilevitz E., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P614, DOI 10.1145/276698.276877

← 1 2 →