Paper Info
Title
On the Farthest Line-Segment Voronoi Diagram.
Abstract
The farthest line-segment Voronoi diagram shows properties surprisingly different from the farthest point Voronoi diagram: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest line-segment hull and its Gaussian map, a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram similarly to the way an ordinary convex hull characterizes the regions of the farthest-point Voronoi diagram. We also derive tighter bounds on the (linear) size of the farthest line-segment Voronoi diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques for the construction of a convex hull to compute the farthest line-segment hull in O(n log n) or output-sensitive O(n log h) time, where n is the number of segments and h is the size of the hull (number of Voronoi faces). As a result, the farthest line-segment Voronoi diagram can be constructed in output sensitive O(n log h) time.
Year
DOI
Venue
2012
10.1007/978-3-642-35261-4_22
ALGORITHMS AND COMPUTATION, ISAAC 2012
Keywords
DocType
Volume
line segment,voronoi diagram
Conference
7676
Issue
ISSN
Citations 
6
0302-9743
2
PageRank 
References 
Authors
0.39
9
2
Name
Order
Citations
PageRank
Evanthia Papadopoulou111018.37
sandeep kumar dey220.72