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 条
  • [1] Agarwal P. K., 1999, Proceedings of the Fifteenth Annual Symposium on Computational Geometry, P143, DOI 10.1145/304893.304960
  • [2] AMIR A, 1999, P 40 ANN IEEE S FOUN, P160
  • [3] Arya S., 1998, J ASS COMPUT MACH, V45
  • [4] ATTALI D, 2001, COMPLEXITY DELAUNAY
  • [5] AURENHAMMER F, 1991, COMPUT SURV, V23, P345, DOI 10.1145/116873.116880
  • [6] PROVABLY GOOD MESH GENERATION
    BERN, M
    EPPSTEIN, D
    GILBERT, J
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (03) : 384 - 409
  • [7] BOAS PV, 1977, INFORMATION PROCESSI, V6, P80
  • [8] A DECOMPOSITION OF MULTIDIMENSIONAL POINT SETS WITH APPLICATIONS TO K-NEAREST-NEIGHBORS AND N-BODY POTENTIAL FIELDS
    CALLAHAN, PB
    KOSARAJU, SR
    [J]. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (01): : 67 - 90
  • [9] CARY M, 2001, OPTIMAL E APPROXIMAT
  • [10] Approximate nearest neighbor queries revisited
    Chan, TM
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1998, 20 (03) : 359 - 373
12