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 条
  • [21] Dynamic Construction of Power Voronoi Diagram
    Tan, Yili
    Li, Lihong
    Wang, Yourong
    INFORMATION COMPUTING AND APPLICATIONS, PT II, 2011, 244 : 660 - +
  • [22] Dynamic Voronoi diagram of complex sites
    Pinto, Francisco de Moura
    Dal Sasso Freitas, Carla Maria
    VISUAL COMPUTER, 2011, 27 (6-8) : 463 - 472
  • [23] Spatial Density Voronoi Diagram and Construction
    Zhao, Ye
    Liu, Shujuan
    Zhang, Youhui
    JOURNAL OF COMPUTERS, 2012, 7 (08) : 2007 - 2014
  • [24] Dynamic Voronoi diagram of complex sites
    Francisco de Moura Pinto
    Carla Maria Dal Sasso Freitas
    The Visual Computer, 2011, 27 : 463 - 472
  • [25] Spontaneous Construction of Voronoi Diagram for Polygon
    Zhao, Ye
    Liu, Xin
    PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON INFORMATION, ELECTRONICS AND COMPUTER, 2014, 59 : 125 - 128
  • [26] UV-diagram: a voronoi diagram for uncertain spatial databases
    Xike Xie
    Reynold Cheng
    Man Lung Yiu
    Liwen Sun
    Jinchuan Chen
    The VLDB Journal, 2013, 22 : 319 - 344
  • [27] Voronoi diagram in optimal path planning
    Bhattacharya, Priyadarshi
    Gavrilova, Marina L.
    ISVD 2007: THE 4TH INTERNATIONAL SYMPOSIUM ON VORONOI DIAGRAMS IN SCIENCE AND ENGINEERING 2007, PROCEEDINGS, 2007, : 38 - +
  • [28] Chemical processor for computation of Voronoi diagram
    Tolmachiev, D
    Adamatzky, A
    ADVANCED MATERIALS FOR OPTICS AND ELECTRONICS, 1996, 6 (04): : 191 - 196
  • [29] Image Segmentation Using Voronoi Diagram
    Dan, Dai
    EIGHTH INTERNATIONAL CONFERENCE ON DIGITAL IMAGE PROCESSING (ICDIP 2016), 2016, 10033
  • [30] Voronoi diagram generation on the ellipsoidal earth
    Hu, Hai
    Liu, XiaoHang
    Hu, Peng
    COMPUTERS & GEOSCIENCES, 2014, 73 : 81 - 87
12345