# Does a robot path have clearance c?

arXiv: https://arxiv.org/abs/1807.09392 · HTML: https://mlsanity.com/paper/1807.09392/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [Olfactory Inertial Odometry: Methodology for Effective Robot Navigation by Scent](https://mlsanity.com/paper/2506.02373/) (2025)

## Abstract (arXiv)

Most path planning problems among polygonal obstacles ask to find a path that avoids the obstacles and is optimal with respect to some measure or a combination of measures, for example an u-to-v shortest path of clearance at least c, where u and v are points in the free space and c is a positive constant. In practical applications, such as emergency interventions/evacuations and medical treatment planning, a number of u-to-v paths are suggested by experts and the question is whether such paths satisfy specific requirements, such as a given clearance from the obstacles. We address the following path query problem: Given a set S of m disjoint simple polygons in the plane, with a total of n vertices, preprocess them so that for a query consisting of a positive constant c and a simple polygonal path π with k vertices, from a point u to a point v in free space, where k is much smaller than n, one can quickly decide whether π has clearance at least c (that is, there is no polygonal obstacle within distance c of π). To do so, we show how to solve the following related problem: Given a set S of m simple polygons in Re2, preprocess S into a data structure so that the polygon in S closest to a query line segment s can be reported quickly. We present an O(t log n) time, O(t) space preprocessing, O((n / √t) log 7/2 n) query time solution for this problem, for any n 1 + ε ≤ t ≤ n2. For a path with k segments, this results in O((n k / √t) log 7/2 n) query time, which is a significant improvement over algorithms that can be derived from existing computational geometry methods when k is small.