Back to Search
Start Over
Computing Skeletons for Rectilinearly Convex Obstacles in the Rectilinear Plane.
- Source :
- Journal of Optimization Theory & Applications; Jul2020, Vol. 186 Issue 1, p102-133, 32p
- Publication Year :
- 2020
-
Abstract
- We introduce the concept of an obstacle skeleton, which is a set of line segments inside a polygonal obstacle ω that can be used in place of ω when performing intersection tests for obstacle-avoiding network problems in the plane. A skeleton can have significantly fewer line segments compared to the number of line segments in the boundary of the original obstacle, and therefore performing intersection tests on a skeleton (rather than the original obstacle) can significantly reduce the CPU time required by algorithms for computing solutions to obstacle-avoidance problems. A minimum skeleton is a skeleton with the smallest possible number of line segments. We provide an exact O (n 2) algorithm for computing minimum skeletons for rectilinear obstacles in the rectilinear plane that are rectilinearly convex. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00223239
- Volume :
- 186
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Journal of Optimization Theory & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 144370826
- Full Text :
- https://doi.org/10.1007/s10957-020-01690-1