@inproceedings{1941df6492ac4f599aa4584d1dd2011a,

title = "On the complexity of minimum-link path problems",

abstract = "We revisit the minimum-link path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings where the min-link path's vertices or edges can be restricted to lie on the boundary of the domain, or can be in its interior. Our results include bit complexity bounds, a novel general hardness construction, and a polynomial-time approximation scheme. We fully characterize the situation in 2D, and provide first results in dimensions 3 and higher for several versions of the problem. Concretely, our results resolve several open problems. We prove that computing the minimum-link diffuse reflection path, motivated by ray tracing in computer graphics, is NP-hard, even for two-dimensional polygonal domains with holes. This has remained an open problem [Ghosh et al. 2012] despite a large body of work on the topic. We also resolve the open problem from [Mitchell et al. 1992] mentioned in the handbook [Goodman and O'Rourke, 2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [Demaine et al. TOPP] (see Problem 22): {"}What is the complexity of the minimum-link path problem in 3-space?{"} Our results imply that the problem is NP-hard even on terrains (and hence, due to discreteness of the answer, there is no FPTAS unless P=NP), but admits a PTAS.",

keywords = "CG, TIN, minimum-linkpath, diffuse reflection, terrain, bit complexity, NP-hardness",

author = "Irina Kostitsyna and Maarten L{\"o}ffler and Frank Staals and Valentin Polishchuk",

year = "2016",

doi = "10.4230/LIPIcs.SoCG.2016.49",

language = "English",

isbn = "978-3-95977-009-5",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik",

pages = "49:1--49:16",

booktitle = "32nd International Symposium on Computational Geometry (SoCG 2016)",

}