# Placing points far away from each other in simple polygon

I am sure the following problem has been studied before, but I did not find any literature about it.

Place m points in a simple polygon such that
the minimum geodesic distance among those points is maximized.


Does anybody know the name of this problem, or has any references?

Maybe the problem corresponds to a known special case of the facility location problem?

• Is it easy in convex polygons? Commented Jun 18, 2012 at 13:11
• @user695652: Good point. In a convex polygon, geodesic distance is just Euclidean distance, and the problem reduces to packing $m$ disks of the largest possible radius such that the disk centers are in the polygon. Commented Jun 18, 2012 at 19:16
• @Joseph O'Rourke I spent quite some time searching for papers dealing with the problem mentioned in your comment, but it seems like not even this case has been studied before. Commented Jun 19, 2012 at 7:47
• @user695652: "Packing Two Disks into a Polygonal Environment" by Bose and Morin is a start. Citeseer link Commented Jun 19, 2012 at 11:22

To more directly address your question, perhaps this is the most natural interpretation for $m=1$:
The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon with $n$ vertices in time $O(n \log n)$.