We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM.
- Authors
PAPADOPOULOU, EVANTHIA; DEY, SANDEEP KUMAR
- Abstract
The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest hull and its Gaussian map as a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and derive tighter bounds on the (linear) size of this diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques to construct a convex hull and compute the farthest hull in O(n n) or output sensitive O(n h) time, where n is the number of line-segments and h is the number of faces in the corresponding farthest Voronoi diagram. As a result, the farthest line-segment Voronoi diagram can be constructed in output sensitive O(n h) time. Our algorithms are given in the Euclidean plane but they hold also in the general Lp metric, 1 ≤ p ≤ ∞.
- Subjects
VORONOI polygons; POLYGONS; PLANE geometry; ANALYTIC geometry of planes; COMPUTATIONAL geometry; GEOMETRY
- Publication
International Journal of Computational Geometry & Applications, 2013, Vol 23, Issue 6, p443
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195913600121