Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon
- Title
- Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon
- Authors
- Oh, E.; AHN, HEE KAP
- Date Issued
- 2017-07-05
- Publisher
- University of Brisbane
- Abstract
- Given a set of sites in a simple polygon, a geodesic Voronoi diagram 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 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. © Eunjin Oh and Hee-Kap Ahn.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/42067
- ISSN
- 1868-8969
- Article Type
- Conference
- Citation
- 33rd International Symposium on Computational Geometry (SoCG 2017), page. 521 - 5215, 2017-07-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.