On the geodesic Voronoi diagram of point sites in a simple polygon
Boris S. Aronov · 1987
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 Voronol diagram of the set of sites using the internal “geodesic” distance inside the polygon as the metric. We describe an Ο((n+k) log2(n+k)) time algorithm for solving this problem and sketch a faster Ο((n+k) log(n+k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.