THE FURTHEST-SITE GEODESIC VORONOI DIAGRAM

Citation
B. Aronov et al., THE FURTHEST-SITE GEODESIC VORONOI DIAGRAM, Discrete & computational geometry, 9(3), 1993, pp. 217-255
Citations number
12
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, Pure","Computer Applications & Cybernetics",Mathematics
ISSN journal
01795376
Volume
9
Issue
3
Year of publication
1993
Pages
217 - 255
Database
ISI
SICI code
0179-5376(1993)9:3<217:TFGVD>2.0.ZU;2-H
Abstract
We present an O((n + k) log(n + k))-time, O(n + k)-space algorithm for computing the furthest-site Voronoi diagram of k point sites with res pect to the geodesic metric within a simple n-sided polygon.