Document Open Access Logo

On the Complexity of Minimum-Link Path Problems

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.49.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Author Details

Irina Kostitsyna
Maarten Löffler
Valentin Polishchuk
Frank Staals

Cite AsGet BibTex

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals. On the Complexity of Minimum-Link Path Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.49

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.
Keywords
  • minimum-linkpath
  • diffuse reflection
  • terrain
  • bit complexity
  • NP-hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. John Adegeest, Mark H. Overmars, and Jack Snoeyink. Minimum-link c-oriented paths: Single-source queries. Int. J. of Computational Geometry and Applications, 4(1):39-51, 1994. Google Scholar
  2. Pankaj K Agarwal and Micha Sharir. Arrangements and their applications. Handbook of computational geometry, pages 49-119, 2000. Google Scholar
  3. Boris Aronov, Alan R. Davis, Tamal K. Dey, Sudebkumar Prasant Pal, and D. Chithra Prasad. Visibility with multiple reflections. Discrete & Computational Geometry, 20(1):61-78, 1998. URL: http://dx.doi.org/10.1007/PL00009378.
  4. Boris Aronov, Alan R. Davis, Tamal K. Dey, Sudebkumar Prasant Pal, and D. Chithra Prasad. Visibility with one reflection. Discrete & Computational Geometry, 19(4):553-574, 1998. URL: http://dx.doi.org/10.1007/PL00009368.
  5. Boris Aronov, Alan R. Davis, John Iacono, and Albert Siu Cheong Yu. The complexity of diffuse reflections in a simple polygon. In Proc. 7th Latin American Symposium on Theoretical Informatics, pages 93-104, 2006. Google Scholar
  6. J. Canny and J. H. Reif. New lower bound techniques for robot motion planning problems. In Proc. 28th Annual Symposium on Foundations of Computer Science, pages 49-60, 1987. Google Scholar
  7. M. de Berg, M. J. van Kreveld, B. J. Nilsson, and M. H. Overmars. Shortest path queries in rectilinear worlds. Int. J. of Computational Geometry and Applications, 3(2):287-309, 1992. Google Scholar
  8. Mark de Berg. Generalized hidden surface removal. Computational Geometry, 5(5):249-276, 1996. URL: http://dx.doi.org/10.1016/0925-7721(95)00008-9.
  9. Erik D. Demaine, Joseph S. B. Mitchell, and Joseph O'Rourke. The open problems project. URL: http://maven.smith.edu/~orourke/TOPP/.
  10. Wei Ding. On computing integral minimum link paths in simple polygons. In EuroCG, 2008. Google Scholar
  11. Alon Efrat, Leonidas J. Guibas, Olaf A. Hall-Holt, and Li Zhang. On incremental rendering of silhouette maps of a polyhedral scene. Computational Geometry: Theory and Applications, 38(3):129-138, 2007. Google Scholar
  12. Dania El-Khechen, Muriel Dulieu, John Iacono, and Nikolaj van Omme. Packing 2 × 2 unit squares into grid polygons is np-complete. In CCCG 2009. Google Scholar
  13. Leila De Floriani and Paola Magillo. Algorithms for visibility computation on terrains: a survey. Environment and Planning B: Planning and Design, 30(5):709-728, 2003. URL: http://EconPapers.repec.org/RePEc:pio:envirb:v:30:y:2003:i:5:p:709-728.
  14. James D. Foley, Richard L. Phillips, John F. Hughes, Andries van Dam, and Steven K. Feiner. Introduction to Computer Graphics. Addison-Wesley Longman Publishing Co., Inc., 1994. Google Scholar
  15. Subir Kumar Ghosh. Computing the visibility polygon from a convex set and related problems. Journal of Algorithms, 12(1):75-95, 1991. Google Scholar
  16. Subir Kumar Ghosh, Partha P. Goswami, Anil Maheshwari, Subhas C. Nandy, Sudebkumar Prasant Pal, and Swami Sarvattomananda. Algorithms for computing diffuse reflection paths in polygons. The Visual Computer, 28(12):1229-1237, 2012. URL: http://dx.doi.org/10.1007/s00371-011-0670-z.
  17. J. E. Goodman and J. O'Rourke. Handbook of Discrete and Computational Geometry. CRC Press series on discrete mathematics and its applications. Chapman &Hall/CRC, 2004. Google Scholar
  18. Leonidas J. Guibas, J. Hershberger, D. Leven, Micha Sharir, and R. E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987. Google Scholar
  19. Leonidas J. Guibas, John Hershberger, Joseph S. B. Mitchell, and Jack Snoeyink. Approximating polygons and subdivisions with minimum link paths. In Proceedings of the 2nd International Symposium on Algorithms, ISA'91, pages 151-162, London, UK, UK, 1991. Springer-Verlag. Google Scholar
  20. J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications, 4:63-98, 1994. Google Scholar
  21. John Hershberger and Jack Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry: Theory and Applications, 4:63-97, 1994. Google Scholar
  22. Ferran Hurtado, Maarten Löffler, Inês Matos, Vera Sacristán, Maria Saumell, Rodrigo I Silveira, and Frank Staals. Terrain visibility with multiple viewpoints. In Proc. 24th International Symposium on Algorithms and Computation, pages 317-327. Springer, 2013. Google Scholar
  23. Simon Kahan and Jack Snoeyink. On the bit complexity of minimum link paths: Superquadratic algorithms for problems solvable in linear time. Computational Geometry: Theory and Applications, 12(1-2):33-44, 1999. Google Scholar
  24. Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals. On the complexity of minimum-link path problems. http://arxiv.org/abs/1603.06972, 2016.
  25. J. S. B. Mitchell, G. Rote, and G. Woeginger. Minimum-link paths among obstacles in the plane. Algorithmica, 8(1):431-459, 1992. Google Scholar
  26. Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski. Minimum-link paths revisited. Computational Geometry: Theory and Applications, 47(6):651-667, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2013.12.005.
  27. Esther Moet. Computation and complexity of visibility in geometric environments. PhD thesis, Utrecht University, 2008. Google Scholar
  28. Christine Piatko. Geometric bicriteria optimal path problems. PhD thesis, Cornell University, 1993. Google Scholar
  29. D. Prasad, S. P. Pal, and T. Dey. Visibility with multiple diffuse reflections. Computational Geometry: Theory and Applications, 10:187-196, 1998. Google Scholar
  30. Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic. Recognizing string graphs in NP. J. Comput. Syst. Sci., 67(2):365-380, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00045-X.
  31. A. James Stewart. Hierarchical visibility in terrains. In Eurographics Rendering Workshop, June 1997. Google Scholar
  32. Subhash Suri. A linear time algorithm with minimum link paths inside a simple polygon. Computer Vision, Graphics and Image Processing, 35(1):99-110, 1986. URL: http://dx.doi.org/10.1016/0734-189X(86)90127-1.
  33. Giovanni Viglietta. Face-guarding polyhedra. In CCCG 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact