Approximate Shortest Paths in Polygons with Violations

DOI10.1142/S0218195920500041MaRDI QIDQ5149572zbMATH OpenOpenAlexFDO

Authors Binayak Dutta, Sasanka Roy

Publication date 11 February 2021

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195920500041

zbMATH Keywords

approximationpolygonsshortest pathsSteiner pointstriangulationviolations

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Approximate shortest paths in polygons with violations
• scientific article; zbMATH DE number 7650244
• Approximate shortest paths in simple polyhedra
• Approximating shortest paths on a nonconvex polyhedron
• Computing approximate shortest paths on convex polytopes
• Shortest Path Queries in Polygonal Domains
• Shortest paths in simple polygons with polygon-meet constraints
• Optimal shortest path queries in a simple polygon
• Shortest path in a polygon using sublinear space
• Shortest Path in a Polygon using Sublinear Space.

Cites work

• A new algorithm for shortest paths among obstacles in the plane
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces
• Approximate shortest descending paths
• Approximate Shortest Paths in Anisotropic Regions
• Approximating shortest paths on weighted polyhedral surfaces
• Computing minimum length paths of a given homotopy class
• Computing shortest paths in the plane with removable obstacles
• Euclidean shortest paths. Exact or approximate algorithms.
• Geometric path problems with violations
• scientific article; zbMATH DE number 2080988 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Practical methods for approximating shortest paths on a convex polytope in \(\mathbb{R}^3\)
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• Shortest paths in the plane with convex polygonal obstacles
• Shortest paths in the plane with obstacle violations
• Shortest paths in the plane with polygonal obstacles
• The Erdős--Nagy theorem and its ramifications
• Triangulating a simple polygon in linear time
• Visibility Algorithms in the Plane

Cited in

(3)

• Geometric path problems with violations
• Approximate shortest paths in polygons with violations
• Distance-preserving approximations of polygonal paths

Describes a project that uses

Uses Software

• BUSHWHACK

This page was built for publication: Approximate Shortest Paths in Polygons with Violations

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