2018/08/13 by Sándor P. Fekete, Fekete, Sándor P., Dominik Krupke +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.1808.04417
openalex publication_date 2018/08/13 · openalex created_date 2022/08/04 · openalex updated_date 2026/07/28
We investigate a variety of problems of finding tours and cycle covers with\nminimum turn cost. Questions of this type have been studied in the past, with\ncomplexity and approximation results as well as open problems dating back to\nwork by Arkin et al. in 2001. A wide spectrum of practical applications have\nrenewed the interest in these questions, and spawned variants: for full\ncoverage, every point has to be covered, for subset coverage, specific points\nhave to be covered, and for penalty coverage, points may be left uncovered by\nincurring an individual penalty.\n We make a number of contributions. We first show that finding a minimum-turn\n(full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the\nlong-standing open Problem 53 in The Open Problems Project edited by Demaine,\nMitchell and O'Rourke. We also prove NP-hardness of finding a subset cycle\ncover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a\npolynomial-time algorithm for full coverage; this shows that their boundary\ntechniques cannot be applied to compute exact solutions for subset and penalty\nvariants.\n On the positive side, we establish the first constant-factor approximation\nalgorithms for all considered subset and penalty problem variants, making use\nof LP/IP techniques. For full coverage in more general grid graphs (e.g.,\nhexagonal grids), our approximation factors are better than the combinatorial\nones of Arkin et al. Our approach can also be extended to other geometric\nvariants, such as scenarios with obstacles and linear combinations of turn and\ndistance costs.\n