Next: Problem 54: Traveling Salesman Problem in Solid Grid Graphs
Previous: Problem 52: Queue-Number of Planar Graphs
What is the complexity of finding a cycle-cover of a planar grid graph that has the fewest possible 90^\circ turns? (An 180^\circ U-turn counts as two turns.) A planar grid graph is a graph whose vertices are any set of points on the planar integer lattice and whose edges connect every pair of vertices at unit distance.
Aggarwal et al. [ACK+97] show that the more general problem of finding a cycle cover for a planar set of points that minimizes total turn angle is NP-hard. Arkin et al. [ABD+01] consider the problem in grid graphs, but are only able to give approximations.
Minimizing turns is a natural geometric measure; understanding its algorithmic behavior is of general interest.
[ABD+01] show that the problem is polynomially solvable when restricted to thin grid graphs, i.e., grid graphs that do not contain an induced 2 \times 2 square. For this special case, the problem behaves somewhat similarly to a Chinese Postman Problem. The problem of finding a minimum-turn tour is known to be NP-complete, even for this special case.
More recent details and related problems can be found in the version [ABD+03].
Minimum-turn cycle cover in a “solid” (genus-zero) grid graph: What is the complexity of finding a minimum-turn tour for a given planar grid graph without holes?
TSP in a solid grid graph: What is the complexity of finding a minimum-length tour for a given planar grid graph without holes? (Problem 54)
traveling salesman; optimization; point sets; graphs
S. P. Fekete, 12 Dec. 2003.
E. M. Arkin, M. A. Bender, E. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia. Optimal covering tours with turn costs. In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, pages 138–147, 2001.
E. M. Arkin, M. A. Bender, E. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia. Optimal covering tours with turn costs. Manuscript (submitted), 2003.
Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber. The angular-metric traveling salesman problem. In Proc. 8thh Annual ACM-SIAM Sympos. Discrete Algorithms, pages 221–229, January 1997.