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

Corresponding Publications

  • On the complexity of minimum-link path problems

    Irina Kostitsyna, Maarten Löffler, Frank Staals, Valentin Polishchuk

    Proc. 32th Annual Symposium on Computational Geometry, 2016
    Invited for a special issue on SoCG 2016 in the Journal of Computational Geometry
    @inproceedings{minlinkpath2016,
      author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                     and Polishchuk, Valentin},
      title = {On the complexity of minimum-link path problems},
      booktitle = {Proc. 32th Annual Symposium on Computational Geometry},
      year = {2016},
      pages = {49:1--49:16},
      isbn = {978-3-95977-009-5},
      issn = {1868-8969},
      volume = {51},
      editor = {S{\'a}ndor Fekete and Anna Lubiw},
      url = {https://dx.doi.org/10.4230/LIPIcs.SoCG.2016.49},
      doi = {10.4230/LIPIcs.SoCG.2016.49},
      location = {Boston, USA},
      numpages = {15},
      keywords = {minimum-link path, diffuse reflection, terrain, bit complexity, NP-hardness reduction},
      series = {Leibniz International Proceedings in Informatics (LIPIcs)},
      publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
      category = {terrains},
      note = {Invited for a special issue on SoCG 2016 in the Journal of Computational Geometry},
    }
    
  • On the complexity of minimum-link path problems

    Irina Kostitsyna, Maarten Löffler, Frank Staals, Valentin Polishchuk

    Journal of Computational Geometry, 2017
    Special issue on SoCG 2016
    @article{minlinkpath2017,
      author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                     and Polishchuk, Valentin},
      title = {On the complexity of minimum-link path problems},
      journal = {Journal of Computational Geometry},
      category = {trajectories},
      year = {2017},
      project = {minlinkpath2016},
      doi = {10.20382/jocg.v8i2},
      url = {https://dx.doi.org/10.20382/jocg.v8i2},
      pages = {80--108},
      numpages = {29},
      volume = {8},
      number = {2},
      note = {Special issue on SoCG 2016},
      project = {minlinkpath2016},
    }
    
  • On the complexity of minimum-link path problems

    Irina Kostitsyna, Maarten Löffler, Frank Staals, Valentin Polishchuk

    Abstr. XVI Spanish Meeting on Computational Geometry, 2015
    @article{minlinkpath_spanishcg2015,
      author = {Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                     and Polishchuk, Valentin},
      title = {On the complexity of minimum-link path problems},
      journal = {Abstr. XVI Spanish Meeting on Computational Geometry},
      year = {2015},
      location = {Barcelona, Spain},
      numpages = {4},
      pages = {21 -- 24},
      url = {http://www-ma2.upc.es/egc15/wp-content/uploads/2013/10/AbstractsXVIEGC.pdf},
      category = {terrains},
      project = {minlinkpath2016},
    }