Shortest path amidst disc obstacles is computable

DOI10.1145/1064092.1064112MaRDI QIDQ5370603zbMATH OpenOpenAlexFDO

Authors Sung Woo Choi, Hyungju Park, Ee-Chien Chang, Do Yong Kwon, Chee K. Yap

Publication date 20 October 2017

Published in Proceedings of the twenty-first annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1064092.1064112

zbMATH Keywords

disc obstaclesexact geometric computationexponential complexityguaranteed precision computationreal RAM modelrobust numerical algorithmsshortest path

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• SHORTEST PATH AMIDST DISC OBSTACLES IS COMPUTABLE
• On the complexity of finding paths in a two-dimensional domain I: Shortest paths
• scientific article; zbMATH DE number 4216992
• Shortest paths in the plane with polygonal obstacles
• New results on shortest paths in three dimensions

Cited in

(4)

• On soft predicates in subdivision motion planning
• SHORTEST PATH AMIDST DISC OBSTACLES IS COMPUTABLE
• An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
• Computing shortest paths amid non-overlapping weighted disks

This page was built for publication: Shortest path amidst disc obstacles is computable

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