12
$\begingroup$

If I sample a large number of uniform points in the unit square and take a traveling salesman tour of them, is there anything at all that can be said/is known about the distribution of angles at each point? The two pictures below show a TSP tour of 1000 points, together with a histogram of the angles. Picture of a TSP TOUR Histogram of angles

It is intuitive that we expect a lot of angles to be near $\pi$, since an angle close to $0$ (or to $2\pi$) suggests that we're "doubling back" on a route and possibly being inefficient.

Improve this question
$\endgroup$
2
  • $\begingroup$ A further question would be how the angles between entering and leaving a sequence of left (resp. right) turns is distributed. As there is a difference of $2\pi$ between cumulated left and right turns, separate statistics may provide further "insights". $\endgroup$
    – Manfred Weis
    Commented Apr 2, 2017 at 6:59
  • 2
    $\begingroup$ Just a tangential remark: There is work on the Dubins' TSP: visiting the points by a vehicle that can only move forward and has a limited turning radius. In some sense, constraining the angle histogram. $\endgroup$
    – Joseph O'Rourke
    Commented Apr 3, 2017 at 0:49

1 Answer 1

Reset to default
2
$\begingroup$

The distribution has a stunning similarity to the density function of random Delaunay angles mentioned on page 4 of The Expected Extremes in a Delaunay Triangulation
Distribution of Angles in Delaunay Triangulations

An explanation might be, that optimal tours go along Delaunay edges for a major part of their course (that heuristic made me search for properties of Delaunay triangulations in the first place).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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