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 条
  • [41] Allocation using a heterogeneous space Voronoi diagram
    Feng, Xin
    Murray, Alan T.
    JOURNAL OF GEOGRAPHICAL SYSTEMS, 2018, 20 (03) : 207 - 226
  • [42] Voronoi Diagram for Intersecting Convex Polygons in the Plane
    Lu J.
    Xiong P.
    Min W.
    Liao Y.
    Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics, 2019, 31 (09): : 1609 - 1616
  • [43] Representation of segment Voronoi diagram by Bezier curves
    L. M. Mestetskii
    Programming and Computer Software, 2015, 41 : 279 - 288
  • [44] On an assignment problem for wireless LAN and the voronoi diagram
    Tamura, Hiroshi
    Sengoku, Masakazu
    Shinoda, Shoji
    SYSTEMS MODELING AND SIMULATION: THEORY AND APPLICATIONS, ASIA SIMULATION CONFERENCE 2006, 2007, : 445 - +
  • [45] Allocation using a heterogeneous space Voronoi diagram
    Xin Feng
    Alan T. Murray
    Journal of Geographical Systems, 2018, 20 : 207 - 226
  • [46] A STRAIGHTFORWARD ITERATIVE ALGORITHM FOR THE PLANAR VORONOI DIAGRAM
    TIPPER, JC
    INFORMATION PROCESSING LETTERS, 1990, 34 (03) : 155 - 160
  • [47] The Hausdorff Voronoi Diagram of Point Clusters in the Plane
    Evanthia Papadopoulou
    Algorithmica , 2004, 40 : 63 - 82
  • [48] Dynamic Construction of the Multiplicatively Weighted Voronoi Diagram
    Liu, Xin
    INTERNATIONAL CONFERENCE ON COMPUTER, NETWORK SECURITY AND COMMUNICATION ENGINEERING (CNSCE 2014), 2014, : 750 - 753
  • [49] FORTRAN PROGRAMS TO CONSTRUCT THE PLANAR VORONOI DIAGRAM
    TIPPER, JC
    COMPUTERS & GEOSCIENCES, 1991, 17 (05) : 597 - 632
  • [50] Voronoi diagram in simply connected complete manifold
    Onishi, K
    Itoh, J
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2002, E85A (05) : 944 - 948
12345