Suppose a set of 2d polygons is given. polygons

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: linked polygons

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 ?


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

  • 1
    $\begingroup$ Thanks for your answer! Sorry for such delay to accept it. I guess my initial description was too broad and your answer is the one which should be accepted. In order to solve the problem (a modified one actually) I used Voronoi diagram to construct proximity graph and extracted a spanning tree from it, so it could be traversed to find a path. Not sure if works in all kind of situations, but it worked out for me. $\endgroup$
    – deephace
    Oct 5 '18 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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