On the complexity of minimum-link path problems

DOI10.4230/LIPICS.SOCG.2016.49MaRDI QIDQ3132885zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

bit-complexitydiffuse reflectionminimum-link pathNP-hardnessterrain

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6707504
• 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

Cited in

(9)

• On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
• Minimal link visibility paths inside a simple polygon
• Minimum-link paths revisited
• scientific article; zbMATH DE number 6707504 (Why is no real title available?)
• The Minimum Reload s-t Path/Trail/Walk Problems
• Link-Length Minimization in Networks
• Global optimization: On pathlengths in min-max graphs
• Structured discrete shape approximation: theoretical complexity and practical algorithm
• The minimum reload \(s-t\) path, trail and walk problems

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)