Problem 53: Minimum-Turn Cycle Cover in Planar Grid Graphs
Statement
What is the complexity of finding a cycle-cover of a planar grid graph
that has the fewest possible 90o turns?
(An 180o 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.
Origin
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.
Status/Conjectures
Open.
Motivation
Minimizing turns is a natural geometric measure;
understanding its algorithmic behavior is of general interest.
Partial and Related Results
[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×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].
Related Open Problems
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)
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.
