### Uittreksel

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.

Taal | Engels |
---|---|

Pagina's | 80-108 |

Aantal pagina's | 29 |

Tijdschrift | Journal of Computational Geometry |

Volume | 8 |

Nummer van het tijdschrift | 2 |

DOI's | |

Status | Gepubliceerd - 2017 |

### Vingerafdruk

### Citeer dit

*Journal of Computational Geometry*,

*8*(2), 80-108. DOI: 10.20382/jocg.v8i2a5

}

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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer 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 -