Polygons tree building by segments linking

Question

Suppose a set of 2d polygons is given.

What I am trying to do is to link all the polygons together by segments in a such way that:

• each of the segments does not intersect any polygons in between (i.e. it connects the "visible" points of the polygon)
• the path along the segments from one polygon to another does not have any loops(if you consider polygons to be the nodes of the graph and the segments to be the edges then the graph has no cycles, i.e. there is a tree of polygons).

For example:

At the moment I am solving the problem by brute force search of the segments from each polygon to all the others checking if there is no intersections in between. And then I am using Kruskal algorithm to find a tree, so the path could be constructed. The solution is ok for "simple" polygons but quite time consuming for more complex ones when the number of vertices and polygons is big.

Are there similar problems or better solutions to this problem ?

Answer 1

This is not a direct hit on your problem (e.g., they allow the path to cross itself), but it illustrates the state of the art:

Polishchuk, Valentin, and Joseph SB Mitchell. "Touring Convex Bodies-A Conic Programming Solution." Cand. Conf. Comput. Geom. 2005. (PDF download.)

---

                   

---

In particular: "Another open problem ([4]) is the hardness of touring a sequence of disjoint non-convex bodies in $\mathbb{R}^2$." So your problem is almost certainly unsolved.

And here is ref. [4]:

M. Dror, A. Efrat, A. Lubiw, and J. S. B. Mitchell. Touring a sequence of polygons. Proceedings 35th ACM Symposium on Theory of Computing, pages 473–482, 2003. ACM Press. (PDF talk slides.)