On the complexity of minimum-link path problems

DOI10.4230/LIPICS.SOCG.2016.49zbMATH Open1387.68265OpenAlexW2465408074MaRDI QIDQ3132885FDOQ3132885

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

Publication date: 30 January 2018

Full work available at URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.49

Recommendations

• scientific article
• Minimal link visibility paths inside a simple polygon
• Minimum-link paths revisited
• On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
• Minimum-link paths among obstacles in the plane

zbMATH Keywords

NP-hardnessterrainbit-complexitydiffuse reflectionminimum-link path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Computational aspects related to convexity (52B55)

Cited In (8)

• Global optimization: On pathlengths in min-max graphs
• Structured discrete shape approximation: theoretical complexity and practical algorithm
• Link-Length Minimization in Networks
• Minimum-link paths revisited
• On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
• The Minimum Reload s-t Path/Trail/Walk Problems
• The minimum reload \(s-t\) path, trail and walk problems
• Title not available (Why is that?)

This page was built for publication: On the complexity of minimum-link path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132885)