2026-08-17T08:42:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5941 2024-03-06T10:37:20Z ddc:004 open_access

On the Complexity of Minimum-Link Path Problems Kostitsyna, Irina Löffler, Maarten Polishchuk, Valentin Staals, Frank minimum-linkpath diffuse reflection terrain bit complexity NP-hardness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Irina Kostitsyna and Maarten Löffler and Valentin Polishchuk and Frank Staals 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.49 urn:nbn:de:0030-drops-59412 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.49 eng https://creativecommons.org/licenses/by/3.0/legalcode