A note on visibility-constrained Voronoi diagrams

被引：2
作者：
Aurenhammer, F. [1 ]
Su, B. [2 ,3 ]
Xu, Y-F [3 ,4 ]
Zhu, B. [5 ]
机构：
[1] Graz Univ Technol, Inst Theoret Comp Sci, A-8010 Graz, Austria
[2] Xian Technol Univ, Sch Econ & Management, Xian 710032, Peoples R China
[3] State Key Lab Mfg Syst Engn, Xian 710049, Peoples R China
[4] Sichuan Univ, Sch Business, Chengdu 610065, Peoples R China
[5] Montana State Univ, Dept Comp Sci, Bozeman, MT 59717 USA
来源：
DISCRETE APPLIED MATHEMATICS | 2014年 / 174卷
基金：
奥地利科学基金会;
关键词：
Voronoi diagram; Visibility; Line arrangement; SHORTEST PATHS; ARRANGEMENTS; COMPLEXITY; LINES; FACES;
D O I：
10.1016/j.dam.2014.04.009
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We consider a variant of visibility-constrained Voronoi diagrams for n given point sites in the Euclidean plane. Whereas such diagrams typically are of size Omega (n(2)), the combinatorial and algorithmic complexity of the studied variant is significantly subquadratic in n. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码：52 / 56
页数：5
相关论文
共 25 条
[1]   Computing many faces in arrangements of lines and segments [J].
Agarwal, PK ;
Matousek, J ;
Schwarzkopf, O .
SIAM JOURNAL ON COMPUTING, 1998, 27 (02) :491-505
[2]  
[Anonymous], P 3 ANN S COMP GEOM
[3]   ON THE GEODESIC VORONOI DIAGRAM OF POINT SITES IN A SIMPLE POLYGON [J].
ARONOV, B .
ALGORITHMICA, 1989, 4 (01) :109-140
[4]   ON THE ZONE OF A SURFACE IN A HYPERPLANE ARRANGEMENT [J].
ARONOV, B ;
PELLEGRINI, M ;
SHARIR, M .
DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (02) :177-186
[5]  
Aurenhammer F., 1991, SIGACT News, V22, P50, DOI 10.1145/126546.126548
[6]  
Aurenhammer F., 2013, Voronoi diagrams and Delaunay triangulations, V8
[7]  
Cheng YX, 2011, LECT NOTES COMPUT SC, V7033, P19
[8]  
Chenglin Fan, 2011, Proceedings of the 2011 Eighth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2011), P127, DOI 10.1109/ISVD.2011.25
[9]  
Chew L P, 1986, PCSTR90147 DEP MATH
[10]  
CHEW LP, 1989, ALGORITHMICA, V4, P97, DOI 10.1007/BF01553881
123