New answers tagged traveling-salesman
0
It's at least as hard as the "Traveling Salesman" problem, that is NP complete: TSP asks whether a salesman can visit n towns while travelling a distance ≤ K. Take the special case of one worker, who can do n jobs in a day if and only he travels a distance ≤ K, then the question "can the single available worker do all jobs in one day" is equivalent to TSP. ...
1
As it is mentioned in this paper, you can find a concave-hull of points in a 2-dimensional plate in $O(n \log n)$ (as complex as finding a convex hull).
Top 50 recent answers are included
