Kostitsyna, Irina ;
Löffler, Maarten ;
Polishchuk, Valentin ;
Staals, Frank
On the Complexity of MinimumLink Path Problems
Abstract
We revisit the minimumlink 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 minlink 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 polynomialtime 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 minimumlink diffuse reflection path, motivated by ray tracing in computer graphics, is NPhard, even for twodimensional 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 minimumlink path problem in 3space?" Our results imply that the problem is NPhard even on terrains (and hence, due to discreteness of the answer, there is no FPTAS unless P=NP), but admits a PTAS.
BibTeX  Entry
@InProceedings{kostitsyna_et_al:LIPIcs:2016:5941,
author = {Irina Kostitsyna and Maarten L{\"o}ffler and Valentin Polishchuk and Frank Staals},
title = {{On the Complexity of MinimumLink Path Problems}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {49:149:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5941},
URN = {urn:nbn:de:0030drops59412},
doi = {10.4230/LIPIcs.SoCG.2016.49},
annote = {Keywords: minimumlinkpath, diffuse reflection, terrain, bit complexity, NPhardness}
}
2016
Keywords: 

minimumlinkpath, diffuse reflection, terrain, bit complexity, NPhardness 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 