Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
I am not sure what do you mean by linear program, is it Delaunay triangulation? –  Anton Petrunin Feb 15 '13 at 2:23
    
@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. –  marc Feb 15 '13 at 2:29
add comment

1 Answer

up vote 1 down vote accepted

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
           (Image from this paper.)

share|improve this answer
    
@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. –  marc Feb 15 '13 at 3:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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