### 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 language | English |
---|---|

Title of host publication | Proc. 32nd International Symposium on Computational Geometry (SoCG) |

Editors | Sándor Fekete, Anna Lubiw |

Place of Publication | Dagstuhl |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 1-16 |

Number of pages | 16 |

ISBN (Print) | 978-3-95977-009-5 |

DOIs | |

Publication status | Published - 2016 |

Event | 32nd International Symposium on Computational Geometry (SoCG 2016) - Boston, United States Duration: 14 Jun 2016 → 18 Jun 2016 |

### Publication series

Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|

Publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik |

Volume | 51 |

### Conference

Conference | 32nd International Symposium on Computational Geometry (SoCG 2016) |
---|---|

Country | United States |

City | Boston |

Period | 14/06/16 → 18/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