Open Access System for Information Sharing

Login Library

 

Article
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon

Title
The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon
Authors
Oh, E.Barba, L.Ahn, H.-K.
Date Issued
May-2020
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
http://oasis.postech.ac.kr/handle/2014.oak/101218
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.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

 AHN, HEE KAP
Grad. School of AI
Read more

Views & Downloads

Browse