A lower bound on Voronoi diagram complexity

被引：10
|
作者：
Aronov, B [1 ]
机构：
[1] Polytech Univ, Dept Comp & Informat Sci, Brooklyn, NY 11201 USA
来源：
INFORMATION PROCESSING LETTERS | 2002年 / 83卷 / 04期
基金：
美国国家科学基金会;
关键词：
Voronoi diagram; computational geometry; computational complexity;
D O I：
10.1016/S0020-0190(01)00336-2
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A lower bound on Voronoi diagram complexity is presented. The Voronoi diagram is a classification of points of the ambient space according to the identity of the closest site or sites. Results provided evidence that the bound derived from envelope analysis is closer to the truth as the conjecture of Sharir does not hold.
引用
收藏
页码：183 / 185
页数：3
相关论文
共 50 条
  • [1] Uncertain Voronoi diagram
    Jooyandeh, Mohammadreza
    Mohades, Ali
    Mirzakhah, Maryam
    INFORMATION PROCESSING LETTERS, 2009, 109 (13) : 709 - 712
  • [2] Aspect-ratio Voronoi diagram and its complexity bounds
    Asano, Tetsuo
    INFORMATION PROCESSING LETTERS, 2007, 105 (01) : 26 - 31
  • [3] An efficient algorithm for construction of the power diagram from the Voronoi diagram in the plane
    Gavrilova, M
    Rokne, J
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1996, 61 (1-2) : 49 - 61
  • [4] Voronoi diagram with visual restriction
    Fan, Chenglin
    Luo, Jun
    Wang, Wencheng
    Zhu, Binhai
    THEORETICAL COMPUTER SCIENCE, 2014, 532 : 31 - 39
  • [5] The Voronoi Diagram of Three Lines
    Hazel Everett
    Daniel Lazard
    Sylvain Lazard
    Mohab Safey El Din
    Discrete & Computational Geometry, 2009, 42 : 94 - 130
  • [6] The Voronoi Diagram of Three Lines
    Everett, Hazel
    Lazard, Daniel
    Lazard, Sylvain
    El Din, Mohab Safey
    DISCRETE & COMPUTATIONAL GEOMETRY, 2009, 42 (01) : 94 - 130
  • [7] Robustness of κ-gon Voronoi diagram construction
    Chen, ZM
    Papadopoulou, E
    Xu, JH
    INFORMATION PROCESSING LETTERS, 2006, 97 (04) : 138 - 145
  • [8] Rounding Voronoi diagram
    Devillers, O
    Gandoin, PM
    THEORETICAL COMPUTER SCIENCE, 2002, 283 (01) : 203 - 221
  • [9] Rounding Voronoi diagram
    Devillers, O
    Gandoin, PM
    DISCRETE GEOMETRY FOR COMPUTER IMAGERY, 1999, 1568 : 375 - 387
  • [10] Fuzzy Voronoi Diagram
    Jooyandeh, Mohammadreza
    Khorasani, Ali Mohades
    ADVANCES IN COMPUTER SCIENCE AND ENGINEERING, 2008, 6 : 82 - 89
12345