Open Access System for Information Sharing

Login Library

 

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

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, H.-K.
Date Issued
Mar-2020
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.
Keywords
LINEAR-TIME ALGORITHMS; SHORTEST-PATH QUERIES; GEODESIC CENTER
URI
http://oasis.postech.ac.kr/handle/2014.oak/101204
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.

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