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 条
  • [31] Voronoi Diagram for services neighboring a highway
    Abellanas, M
    Hurtado, F
    Sacristán, V
    Icking, C
    Ma, L
    Klein, R
    Langetepe, E
    Palop, B
    INFORMATION PROCESSING LETTERS, 2003, 86 (05) : 283 - 288
  • [32] OPTIMAL CONSTRUCTION OF THE CITY VORONOI DIAGRAM
    Bae, Sang Won
    Kim, Jae-Hoon
    Chwa, Kyung-Yong
    INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2009, 19 (02) : 95 - 117
  • [33] UV-diagram: a voronoi diagram for uncertain spatial databases
    Xie, Xike
    Cheng, Reynold
    Yiu, Man Lung
    Sun, Liwen
    Chen, Jinchuan
    VLDB JOURNAL, 2013, 22 (03) : 319 - 344
  • [34] Improved lower bound for the complexity of unique shortest vector problem
    Baolong Jin
    Rui Xue
    Cybersecurity, 6
  • [35] A large lower bound on the query complexity of a simple boolean function
    Bollig, B
    INFORMATION PROCESSING LETTERS, 2005, 95 (04) : 423 - 428
  • [36] Improved lower bound for the complexity of unique shortest vector problem
    Jin, Baolong
    Xue, Rui
    CYBERSECURITY, 2023, 6 (01)
  • [37] An improved lower bound on query complexity for quantum PAC learning
    Zhang, Chi
    INFORMATION PROCESSING LETTERS, 2010, 111 (01) : 40 - 45
  • [38] Cosmological lower bound on the circuit complexity of a small problem in logic
    Stockmeyer, L
    Meyer, AR
    JOURNAL OF THE ACM, 2002, 49 (06) : 753 - 784
  • [39] Dynamic Construction of Voronoi Diagram for Figures
    Zhao, Ye
    Zhang, Yajing
    2009 IEEE 10TH INTERNATIONAL CONFERENCE ON COMPUTER-AIDED INDUSTRIAL DESIGN & CONCEPTUAL DESIGN, VOLS 1-3: E-BUSINESS, CREATIVE DESIGN, MANUFACTURING - CAID&CD'2009, 2009, : 2189 - +
  • [40] Algorithm of 2D-Voronoi Diagram Construction With Rectangular Block
    Sinharay, Arindam
    Saha, Antara
    Roy, Tanusree
    Pande, Vaswar
    2016 3rd International Conference on Recent Advances in Information Technology (RAIT), 2016, : 582 - 585
12345