# 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? Jun 18 '12 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. Jun 18 '12 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. Jun 19 '12 at 7:47
• @user695652: "Packing Two Disks into a Polygonal Environment" by Bose and Morin is a start. Citeseer link Jun 19 '12 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)$.