7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Is it easy in convex polygons? $\endgroup$
    – 101011
    Jun 18 '12 at 13:11
  • $\begingroup$ @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. $\endgroup$
    – Joseph O'Rourke
    Jun 18 '12 at 19:16
  • $\begingroup$ @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. $\endgroup$
    – 101011
    Jun 19 '12 at 7:47
  • $\begingroup$ @user695652: "Packing Two Disks into a Polygonal Environment" by Bose and Morin is a start. Citeseer link $\endgroup$
    – Joseph O'Rourke
    Jun 19 '12 at 11:22
4
$\begingroup$

This does not answer your (interesting) question, but it may be worth mentioning that this variant (which does not use geodesic distance) has been studied:

Thomas Shermer, "Hiding people in polygons," Computing, Volume 42, Numbers 2-3 (1989), 109-131 (Springer link):

A hidden set is a set of points such that no two points in the set are visible to each other. A hidden guard set is a hidden set which is also a guard set. In this paper we consider the problem for finding hidden sets and hidden guard sets in and around polygons. In particular, we establish bounds on the maximum size of hidden sets, and show that the problem of finding a maximum hidden set is NP-hard.

To more directly address your question, perhaps this is the most natural interpretation for $m=1$:

Pollack, Sharir, Rote, "Computing the Geodesic Center of a Simple Polygon," Discrete Comput. Geom. 4:611-626 (1989):

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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.