On the complexity of minimum-link path problems

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

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 vertices and/or the edges of the path are 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 2 dimensions, and provide first results in dimensions 3 and higher for several variants 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 Rourke'2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [http://maven.smith.edu/~orourke/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.
TaalEngels
Pagina's80-108
Aantal pagina's29
TijdschriftJournal of Computational Geometry
Volume8
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - 2017

Vingerafdruk

Ray tracing
Computer graphics
Telecommunication links
Computational complexity
Hardness
Polynomials

Citeer dit

Kostitsyna, I., Löffler, M., Polishchuk, V., & Staals, F. (2017). On the complexity of minimum-link path problems. Journal of Computational Geometry, 8(2), 80-108. DOI: 10.20382/jocg.v8i2a5
Kostitsyna, I. ; Löffler, M. ; Polishchuk, V. ; Staals, F./ On the complexity of minimum-link path problems. In: Journal of Computational Geometry. 2017 ; Vol. 8, Nr. 2. blz. 80-108
@article{ffd7e1da04444b71b8d314c6e3c0a909,
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 vertices and/or the edges of the path are 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 2 dimensions, and provide first results in dimensions 3 and higher for several variants 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 Rourke'2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [http://maven.smith.edu/~orourke/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.",
author = "I. Kostitsyna and M. L{\"o}ffler and V. Polishchuk and F. Staals",
year = "2017",
doi = "10.20382/jocg.v8i2a5",
language = "English",
volume = "8",
pages = "80--108",
journal = "Journal of Computational Geometry",
issn = "1920-180X",
publisher = "Macodrum library, Carleton University",
number = "2",

}

Kostitsyna, I, Löffler, M, Polishchuk, V & Staals, F 2017, 'On the complexity of minimum-link path problems' Journal of Computational Geometry, vol. 8, nr. 2, blz. 80-108. DOI: 10.20382/jocg.v8i2a5

On the complexity of minimum-link path problems. / Kostitsyna, I.; Löffler, M.; Polishchuk, V.; Staals, F.

In: Journal of Computational Geometry, Vol. 8, Nr. 2, 2017, blz. 80-108.

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

TY - JOUR

T1 - On the complexity of minimum-link path problems

AU - Kostitsyna,I.

AU - Löffler,M.

AU - Polishchuk,V.

AU - Staals,F.

PY - 2017

Y1 - 2017

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 vertices and/or the edges of the path are 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 2 dimensions, and provide first results in dimensions 3 and higher for several variants 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 Rourke'2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [http://maven.smith.edu/~orourke/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 vertices and/or the edges of the path are 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 2 dimensions, and provide first results in dimensions 3 and higher for several variants 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 Rourke'2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [http://maven.smith.edu/~orourke/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.20382/jocg.v8i2a5

DO - 10.20382/jocg.v8i2a5

M3 - Article

VL - 8

SP - 80

EP - 108

JO - Journal of Computational Geometry

T2 - Journal of Computational Geometry

JF - Journal of Computational Geometry

SN - 1920-180X

IS - 2

ER -

Kostitsyna I, Löffler M, Polishchuk V, Staals F. On the complexity of minimum-link path problems. Journal of Computational Geometry. 2017;8(2):80-108. Beschikbaar vanaf, DOI: 10.20382/jocg.v8i2a5