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