  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 2D, 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 [1] despite a large body of work on
the topic. We also resolve the open problem from [2] mentioned in the handbook
[3] (see Chapter 27.5, Open problem 3) and The Open Problems Project [4] (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.
