Abstract
Given a simple polygon with n sides in the plane and a set of k 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 an O((n + k) log(n + k) log n)-time algorithm for solving this problem and sketch a faster O((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.
Original language | English (US) |
---|---|
Pages (from-to) | 109-140 |
Number of pages | 32 |
Journal | Algorithmica |
Volume | 4 |
Issue number | 1 |
DOIs | |
State | Published - Dec 1989 |
Keywords
- Computational geometry
- Geodesic metric
- Shortest paths
- Simple polygons
- Voronoi diagrams
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics