Paper Info
Title
Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures.
Abstract
We present linear-time algorithms to construct tree-like Voronoi diagrams with disconnected regions after the sequence of their faces along an enclosing boundary (or at infinity) is known. We focus on the farthest-segment Voronoi diagram, however, our techniques are also applicable to constructing the order-(k+1) subdivision within an order-k Voronoi region of segments and updating a nearest-neighbor Voronoi diagram of segments after deletion of one site. Although tree-structured, these diagrams illustrate properties surprisingly different from their counterparts for points. The sequence of their faces along the relevant boundary forms a Davenport-Schinzel sequence of order >= 2. Once this sequence is known, we show how to compute the corresponding Voronoi diagram in linear time, expected or deterministic, augmenting the existing linear-time frameworks for points in convex position with the ability to handle non-point sites and multiple Voronoi faces.
Year
DOI
Venue
2015
10.1007/978-3-662-48971-0_35
ALGORITHMS AND COMPUTATION, ISAAC 2015
DocType
Volume
ISSN
Conference
9472
0302-9743
Citations 
PageRank 
References 
3
0.40
6
Authors
2
Name
Order
Citations
PageRank
Elena Khramtcova174.24
Evanthia Papadopoulou211018.37