I'm confused about how the bead-tiling algorithm for the Dubins' TSP from this article works:

On the Dubins Traveling Salesperson Problems: novel approximation algorithms
Ketan Savla, Emilio Frazzoli, Francesco Bullo

What does the algorithm return? Does it return this path that has been going over all (meta-)beads almost log2(n) times? Or only the final path obtained from the last recursive phase?

a Dubins tour is constructed with the following properties: ...
This process is iterated ⌈log2n⌉ times, ...

Also, does this result path go back to the top left corner since it started there? If yes, why waste some length of our path to go back to the top, instead of going to the first node encountered to obtain our Dubins tour?

... it visits all (meta-bead) rows in sequence top-to-down, alternating between left-to-right and right-to-left passes, ...

A minor issue is also the complexity stated. it states the computational complexity is of order n. I personally thought it to be so much more.

The computational complexity of the RECURSIVE BEAD-TILING ALGORITHM is of order n.

All in all, to express it in one simple question :
What does the bead-tiling algorithm do?

  • $\begingroup$ @D.W. is it better now? I formulated a simple question at the end, but stated the main difficulties I have understanding the algorithm above. $\endgroup$ – J. Schmidt Mar 7 '17 at 8:29
  • $\begingroup$ Much better! Thanks for the edit. Hope you get a useful answer! $\endgroup$ – D.W. Mar 7 '17 at 16:05

Your Answer

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

Browse other questions tagged or ask your own question.