On the complexity of minimum-link path problems

I. Kostitsyna, M. Löffler, V. Polishchuk, F. Staals

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
22 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProc. 32nd International Symposium on Computational Geometry (SoCG)
EditorsSándor Fekete, Anna Lubiw
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-16
Number of pages16
ISBN (Print)978-3-95977-009-5
DOIs
Publication statusPublished - 2016
Event32nd International Symposium on Computational Geometry (SoCG 2016) - Boston, United States
Duration: 14 Jun 201618 Jun 2016

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume51

Conference

Conference32nd International Symposium on Computational Geometry (SoCG 2016)
CountryUnited States
CityBoston
Period14/06/1618/06/16

Fingerprint Dive into the research topics of 'On the complexity of minimum-link path problems'. Together they form a unique fingerprint.

  • Cite this

    Kostitsyna, I., Löffler, M., Polishchuk, V., & Staals, F. (2016). On the complexity of minimum-link path problems. In S. Fekete, & A. Lubiw (Eds.), Proc. 32nd International Symposium on Computational Geometry (SoCG) (pp. 1-16). [49] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 51). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2016.49