The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon
SCIE
SCOPUS
- Title
- The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon
- Authors
- Oh, E.; Barba, L.; Ahn, H.-K.
- Date Issued
- 2020-05
- Publisher
- SPRINGER
- Abstract
- Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O(nloglogn+mlogm)-time algorithm to compute the geodesic farthest-point Voronoi diagram of m point sites in a simple n-gon. This improves the previously best known algorithm by Aronov et al. (Discrete Comput Geom 9(3):217-255, 1993). In the case that all point sites are on the boundary of the simple polygon, we can compute the geodesic farthest-point Voronoi diagram in O((n+m)loglogn) time.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/101218
- DOI
- 10.1007/s00453-019-00651-z
- ISSN
- 0178-4617
- Article Type
- Article
- Citation
- ALGORITHMICA, vol. 82, no. 5, page. 1434 - 1473, 2020-05
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.