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

<p>Thomas Shermer, "Hiding people in polygons,"
<em>Computing</em>,
Volume 42, Numbers 2-3 (1989), 109-131 (<a href="http://www.springerlink.com/content/p87416004583tr0r/" rel="nofollow">Springer link</a>):</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

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

<blockquote>
  <p>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)$.</p>
</blockquote>

CC BY-SA 3.0
2012-06-18T00:20:45.287Z
2012-06-18T00:25:52.983Z
2012-06-18T00:25:52.983Z
Joseph O'Rourke
<p>I am sure the following problem has been studied before, but I did not find any literature about it.</p>

<pre><code>Place m points in a simple polygon such that 
the minimum geodesic distance among those points is maximized.
</code></pre>

<p>Does anybody know the name of this problem, or has any references?</p>

<p>Maybe the problem corresponds to a known special case of the facility location problem?</p>

CC BY-SA 3.0
2012-06-18T13:11:47.163Z
Is it easy in convex polygons?
101011
CC BY-SA 3.0
2012-06-18T19:16:12.617Z
@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
CC BY-SA 3.0
2012-06-19T07:47:08.010Z
@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
CC BY-SA 3.0
2012-06-19T11:22:37.353Z
@user695652: "Packing Two Disks into a Polygonal Environment" by Bose and Morin is a start. [Citeseer link](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.5276)
Joseph O'Rourke
<reference-request><cg.comp-geom>
Placing points far away from each other in simple polygon
Joe
# Placing points far away from each other in simple polygon

(Asked by: username_0 on 2012-06-17)

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?

**Tags:** reference-request, cg.comp-geom

> **Comments:**
> **username_1**: Is it easy in convex polygons?  
> **username_2**: @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.  
> **username_1**: @username_2 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.  
> **username_2**: @user695652: "Packing Two Disks into a Polygonal Environment" by Bose and Morin is a start. [Citeseer link](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.5276)  

---

## 1 answers

### Answer by username_2 on 2012-06-18. Score: 4

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](http://www.springerlink.com/content/p87416004583tr0r/)):

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


---

