An efficient algorithm for computing high-quality paths amid polygonal obstacles

DOI10.1137/1.9781611974331.CH82MaRDI QIDQ4575663zbMATH OpenOpenAlexFDO

Authors Kyle Fox, Oren Salzman, Pankaj K. Agarwal

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.02939

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We study a path-planning problem amid a set $mathcalO$ of obstacles in $mathbb{R}^2$, in which we wish to compute a short path between two points while also maintaining a high clearance from $mathcalO$; the clearance of a point is its distance from a nearest obstacle in $mathcalO$. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let $n$ be the total number of obstacle vertices and let $varepsilonin(0,1]$. Our algorithm computes in time $O(frac{n}^{2}varepsilo{n}^{2}logfracnvarepsilon)$ a path of total cost at most $(1+varepsilon)$ times the cost of the optimal path.

Recommendations

• An efficient algorithm for computing high-quality paths amid polygonal obstacles
• Does a robot path have clearance C?
• Shortest paths in the plane with polygonal obstacles
• scientific article; zbMATH DE number 871939
• A Polynomial-Time Algorithm for Computing Shortest Paths of Bounded Curvature Amidst Moderate Obstacles

Cited in

(8)

• Routing among convex polygonal obstacles in the plane
• Does a robot path have clearance C?
• An iterative algorithm to determine the number of time steps in path generation methods
• Dynamic and robust local clearance triangulations
• Efficiently approximating polygonal paths in three and higher dimensions
• The application of \(\psi\)-transform for determining a near-optimal path in the presence of polyhedral obstacles
• An efficient algorithm for computing high-quality paths amid polygonal obstacles
• A convex polygon among polygonal obstacle: Placement and high-clearance motion

This page was built for publication: An efficient algorithm for computing high-quality paths amid polygonal obstacles

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