On Higher Order Voronoi Diagrams of Line Segments

被引:0
作者
Papadopoulou, Evanthia [1 ]
Zavershynskyi, Maksym [1 ]
机构
[1] Univ Svizzera Italiana, Fac Informat, Lugano, Switzerland
来源
ALGORITHMS AND COMPUTATION, ISAAC 2012 | 2012年 / 7676卷
关键词
computational geometry; Voronoi diagrams; line segments; higher order Voronoi diagrams; PLANE; SET;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We analyze structural properties of the order-k Voronoi diagram of line segments, which surprisingly has not received any attention in the computational geometry literature. We show that order-k Voronoi regions of line segments may be disconnected; in fact a single order-k Voronoi region may consist of Omega(n) disjoint faces. Nevertheless, the structural complexity of the order-k Voronoi diagram of non-intersecting segments remains O(k(n -k)) similarly to points. For intersecting line segments the structural complexity remains O(k(n -k)) for k >= n/2.
引用
收藏
页码:177 / 186
页数:10
相关论文
共 50 条
[1]   The Higher-Order Voronoi Diagram of Line Segments [J].
Papadopoulou, Evanthia ;
Zavershynskyi, Maksym .
ALGORITHMICA, 2016, 74 (01) :415-439
[2]   The Higher-Order Voronoi Diagram of Line Segments [J].
Evanthia Papadopoulou ;
Maksym Zavershynskyi .
Algorithmica, 2016, 74 :415-439
[3]   On the Complexity of Higher Order Abstract Voronoi Diagrams [J].
Bohler, Cecilia ;
Cheilaris, Panagiotis ;
Klein, Rolf ;
Liu, Chih-Hung ;
Papadopoulou, Evanthia ;
Zavershynskyi, Maksym .
AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2013, 7965 :208-219
[4]   On the complexity of higher order abstract Voronoi diagrams [J].
Bohler, Cecilia ;
Cheilaris, Panagiotis ;
Klein, Rolf ;
Liu, Chih-Hung ;
Papadopoulou, Evanthia ;
Zavershynskyi, Maksym .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2015, 48 (08) :539-551
[5]   Unbounded Regions of High-Order Voronoi Diagrams of Lines and Line Segments in Higher Dimensions [J].
Barequet, Gill ;
Papadopoulou, Evanthia ;
Suderland, Martin .
DISCRETE & COMPUTATIONAL GEOMETRY, 2024, 72 (03) :1304-1332
[6]   A Faster Algorithm of Higher Order Voronoi Diagrams [J].
Hu, Lixia ;
Liu, Hongjuan ;
Xu, Baiquan .
2015 SEVENTH INTERNATIONAL CONFERENCE ON MEASURING TECHNOLOGY AND MECHATRONICS AUTOMATION (ICMTMA 2015), 2015, :6-9
[7]   A Sweepline Algorithm for Higher Order Voronoi Diagrams [J].
Zavershynskyi, Maksym ;
Papadopoulou, Evanthia .
2013 TENTH INTERNATIONAL SYMPOSIUM ON VORONOI DIAGRAMS IN SCIENCE AND ENGINEERING (ISVD), 2013, :16-22
[8]   Voronoi diagrams on line segments:: Measurements for contextual generalization purposes [J].
Hangouët, JF ;
Djadri, R .
SPATIAL INFORMATION THEORY: A THEORETICAL BASIC FOR GIS, 1997, 1329 :207-222
[9]   Swap conditions for dynamic Voronoi diagrams for circles and line segments [J].
Gavrilova, M ;
Rokne, J .
COMPUTER AIDED GEOMETRIC DESIGN, 1999, 16 (02) :89-106
[10]   A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS [J].
Aurenhammer, Franz ;
Schwarzkopf, Otfried .
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1992, 2 (04) :363-381