Computing shortest paths amid convex pseudodisks

DOI10.1137/110840030MaRDI QIDQ2848214zbMATH OpenOpenAlexFDO

Authors Danny Z. Chen, Haitao Wang, John Hershberger

Publication date 25 September 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110840030

zbMATH Keywords

convex obstaclesEuclidean distancemotion planningpseudodisksshortest pathsvisibility graphs

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• Computing shortest paths amid pseudodisks
• Shortest paths in the plane with convex polygonal obstacles
• Time and space efficient algorithms for shortest paths between convex polygons
• Shortest paths in the plane with polygonal obstacles
• An O(n2) shortest path algorithm for a non-rotating convex body

Cited in

(9)

• Visibility graphs, dismantlability, and the cops and robbers game
• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• SHORTEST PATH AMIDST DISC OBSTACLES IS COMPUTABLE
• scientific article; zbMATH DE number 176771 (Why is no real title available?)
• Computing shortest paths in the plane with removable obstacles
• Computing shortest paths amid pseudodisks
• An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
• Computing shortest paths amid non-overlapping weighted disks
• A new algorithm for Euclidean shortest paths in the plane

This page was built for publication: Computing shortest paths amid convex pseudodisks

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