Finding a point farthest away from $k$ points in a polygon

Question

There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.

I guess one way of attacking the problem would be through a linear program, but this looks a bit messy. Does anybody have any other ideas for an algorithm?

Answer 1

I may be misunderstanding your question, but could it(?) be rephrased as:

Find the largest empty disk (containing none of the $k$ points) whose center lies inside the polygon $P$.

If this is a correct interpretation, let $S$ be the set of your $k$ points. Compute the Voronoi diagram of $S$, and intersect it with the polygon $P$, clipping all portions of the diagram exterior to $P$. Then your optimal center lies either at an interior Voronoi vertex, or at a vertex of $P$, or where a Voronoi edge crosses the boundary of $P$. You could check each such point.

---

The above solution assumes "distance" is Euclidean distance. But it is now clear from the OP's comment below that he is measuring distance by the shortest path within the polygon. And so the relevant object is the geodesic Voronoi diagram, just as he says:

Boris Aronov. "On the geodesic Voronoi diagram of point sites in a simple polygon." Algorithmica (1989) 4:109-140. (ACM link)

           _(source)

           _{(Image from this paper.)}