Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon
SCIE
SCOPUS
- Title
- Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon
- Authors
- Oh, E.; Ahn, H.-K.
- Date Issued
- 2020-03
- Publisher
- SPRINGER
- Abstract
- Given a set of sites in a simple polygon, a geodesic Voronoi diagram of the sites partitions the polygon into regions based on distances to sites under the geodesic metric. We present algorithms for computing the geodesic nearest-point, higher-order and farthest-point Voronoi diagrams of m point sites in a simple n-gon, which improve the best known ones for m <= n/polylog n. Moreover, the algorithms for the geodesic nearest-point and farthest-point Voronoi diagrams are optimal for m <= n/polylog n. This partially answers a question posed by Mitchell in the Handbook of Computational Geometry.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/101204
- DOI
- 10.1007/s00454-019-00063-4
- ISSN
- 0179-5376
- Article Type
- Article
- Citation
- DISCRETE & COMPUTATIONAL GEOMETRY, vol. 63, no. 2, page. 418 - 454, 2020-03
- 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.