On the geodesic voronoi diagram of point sites in a simple polygon |
| |
Authors: | Boris Aronov |
| |
Affiliation: | 1. Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012, New York, NY, USA
|
| |
Abstract: | Given a simple polygon withn sides in the plane and a set ofk point “sites” in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal “geodesic” distance inside the polygon as the metric. We describe anO((n + k) log(n + k) logn)-time algorithm for solving this problem and sketch a fasterO((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|