2
$\begingroup$

There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.

I guess one way of attacking the problem would be through a linear program, but this looks a bit messy. Does anybody have any other ideas for an algorithm?

$\endgroup$
2
  • $\begingroup$ I am not sure what do you mean by linear program, is it Delaunay triangulation? $\endgroup$ Feb 15, 2013 at 2:23
  • $\begingroup$ @Anton Petrunin I meant that maybe this optimization problem can be stated as a linear program (en.wikipedia.org/wiki/Linear_programming ) but I don't think that would be the right way to attack it. $\endgroup$
    – marc
    Feb 15, 2013 at 2:29

1 Answer 1

3
$\begingroup$

I may be misunderstanding your question, but could it(?) be rephrased as:

Find the largest empty disk (containing none of the $k$ points) whose center lies inside the polygon $P$.

If this is a correct interpretation, let $S$ be the set of your $k$ points. Compute the Voronoi diagram of $S$, and intersect it with the polygon $P$, clipping all portions of the diagram exterior to $P$. Then your optimal center lies either at an interior Voronoi vertex, or at a vertex of $P$, or where a Voronoi edge crosses the boundary of $P$. You could check each such point.


The above solution assumes "distance" is Euclidean distance. But it is now clear from the OP's comment below that he is measuring distance by the shortest path within the polygon. And so the relevant object is the geodesic Voronoi diagram, just as he says:

Boris Aronov. "On the geodesic Voronoi diagram of point sites in a simple polygon." Algorithmica (1989) 4:109-140. (ACM link)


           VorDiag (source)

           (Image from this paper.)

$\endgroup$
1
  • $\begingroup$ @Joseph O'Rourke If we replace the word disk by geodesic disk, then yes my problem is equivalent to your formulation. I guess your solution still works by just using a geodesic Voronoi diagram. $\endgroup$
    – marc
    Feb 15, 2013 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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