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

zbMATH Keywords

shortest pathsvisibilitypolygonal obstaclescontinuous Dijkstraobstacle crossing

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

• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• 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
• 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
• k-violation linear programming

Cited in

(11)

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

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)