TY - GEN

T1 - On the complexity of minimum-link path problems

AU - Kostitsyna, I.

AU - Löffler, M.

AU - Polishchuk, V.

AU - Staals, F.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.SoCG.2016.49

DO - 10.4230/LIPIcs.SoCG.2016.49

M3 - Conference contribution

SN - 978-3-95977-009-5

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 16

BT - Proc. 32nd International Symposium on Computational Geometry (SoCG)

A2 - Fekete, Sándor

A2 - Lubiw, Anna

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

T2 - 32nd International Symposium on Computational Geometry (SoCG 2016)

Y2 - 14 June 2016 through 18 June 2016

ER -