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] 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

[5] 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

[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

← 1 2 3 4 5 →