Shortest paths in the plane with obstacle violations

DOI10.4230/LIPICS.ESA.2017.49MaRDI QIDQ5111738zbMATH OpenFDO

Authors Neeraj Kumar, John Hershberger, Subhash Suri

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2017.49

zbMATH Keywords

continuous Dijkstraobstacle crossingpolygonal obstaclesshortest pathsvisibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Shortest paths in the plane with obstacle violations
• Shortest paths in the plane with convex polygonal obstacles
• Shortest paths in the plane with polygonal obstacles
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE

Cites work

• k-violation linear programming
• A near-optimal algorithm for shortest paths among curved obstacles in the plane
• A new algorithm for shortest paths among obstacles in the plane
• Algorithms and Computation
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Augmenting the connectivity of geometric graphs
• Computing minimum length paths of a given homotopy class
• Computing shortest paths among curved obstacles in the plane
• Euclidean shortest paths in the presence of rectilinear barriers
• Geometric k Shortest Paths
• Geometric path problems with violations
• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Low-Dimensional Linear Programming with Violations
• Network flows. Theory, algorithms, and applications.
• On geometric optimization with few violated constraints
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• Shortest paths in the plane with convex polygonal obstacles
• Shortest paths in the plane with polygonal obstacles
• The weighted region problem
• Visibility of disjoint polygons

Cited in

(11)

• k-th shortest collision-free path planning
• Geometric path problems with violations
• Shortest paths among transient obstacles
• Approximate shortest paths in polygons with violations
• Shortest paths in the plane with obstacle violations
• Improved approximation bounds for the minimum constraint removal problem
• scientific article; zbMATH DE number 4216992 (Why is no real title available?)
• How to navigate through obstacles?
• Computing shortest paths in the plane with removable obstacles
• Approximate Shortest Paths in Polygons with Violations
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE

This page was built for publication: Shortest paths in the plane with obstacle violations

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