Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

enter image description here

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$:

enter image description here

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)?

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer

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.