[Solved]: Finding a way out of a polygon

Problem Detail: 

There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,\dots,D_n$:

The goal is to select one of the polygons, say $D_i$, and attach to it a polygon $E_i$ such that:

• $D_i\cup E_i$ is still simply-connected.
• $E_i$ is interior-disjoint from all other polygons $D_i$.
• $D_i\cup E_i$ is connected with the exterior of $C$:

Is there an algorithm, preferably published, that solves this problem in time polynomial in the representation of the problem (e.g. total number of vertices of all polygons)?

Asked By : Erel Segal-Halevi

Answered By : Shreesh

Basically this is shortest path problem in polygon with holes. There is no constraint in taking $E_i$ as a path of negligible width.

If you just want to connect internal holes to outside boundary without caring about the path length, then just take any point on the boundary of interior hole and calculate a path to any point on the outer boundary. I don't know your application, but probably you are looking for minimum link rather than minimum euclidean distance, in that case minimum link path would be better.

References:
1) S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing archive Volume 20 Issue 5, Oct. 1991 Pages 888-910 (for shortest paths among obstacles)
2) J. Hershberger and S. Suri. Efficient computation of Euclidean shortest paths in the plane. In Proc. 34th Annu. IEEE Sympos. 1993.
3) Joseph S. B. Mitchell, Günter Rote, and Gerhard Woeginger: Minimum-link paths among obstacles in the plane. Algorithmica 8 (1992), 431-459.

However, I should warn you, all the implementations for shortest path, or shortest link path use triangulation for which the optimal algorithm is not very practical. You can however use any sub-optimal algorithm which may be more efficient for your purpose.

The above algorithms are all polynomial in input size.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52916