Estivill-Castro, V. (Vladimir)Heednacram, ApichatSuraweera, Francis2020-03-122020-03-122011Estivill-Castro V, Heednacram A, Suraweera F. FPT-algorithms for minimum-bends tours. Int J Comput Geom Appl. 2011 Apr;21(2):189-213. DOI: 10.1142/S02181959110036150218-1959http://hdl.handle.net/10230/43890This paper discusses the κ-BENDS TRAVELING SALESMAN PROBLEM. In this NP-complete problem, the inputs are n points in the plane and a positive integer κ, and we are asked whether we can travel in straight lines through these n points with at most κ bends. There are a number of applications where minimizing the number of bends in the tour is desirable because bends are considered very costly. We prove that this problem is fixed-parameter tractable (FPT). The proof is based on the kernelization approach. We also consider the RECTILINEAR κ-BENDS TRAVELING SALESMAN PROBLEM, which requires that the line-segments be axis-parallel.1 Note that a rectilinear tour with κ bends is a cover with κ-line segments, and therefore a cover by lines. We introduce two types of constraints derived from the distinction between line-segments and lines. We derive FPT-algorithms with different techniques and improved time complexity for these cases.application/pdfengElectronic version of an article published as International Journal of Computational Geometry and Applications 2011 Apr;21(2):189-213. DOI: 10.1142/S0218195911003615 © copyright World Scientific Publishing Company https://www.worldscientific.com/worldscinet/ijcgainfo:eu-repo/semantics/articlehttp://dx.doi.org/10.1142/S0218195911003615Computational geometryFixed-parameter tractableMinimum-bends toursCovering with hyperplanesinfo:eu-repo/semantics/openAccess