On the geodesic Voronoi diagram of point sites in a simple polygon (Q1115602)

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.