Sampling-based bottleneck pathfinding with applications to Frechet matching

Abstract

We describe a general probabilistic framework to address a variety of Frechet-distance optimization problems. Specifically, we are interested in finding minimal bottleneck-paths in $d$-dimensional Euclidean space between given start and goal points, namely paths that minimize the maximal value over a continuous cost map. We present an efficient and simple sampling-based framework for this problem, which is inspired by, and draws ideas from, techniques for robot motion planning. We extend the framework to handle not only standard bottleneck pathfinding, but also the more demanding case, where the path needs to be monotone in all dimensions. Finally, we provide experimental results of the framework on several types of problems.

References in corpus (5)

• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
• Motion Planning for Unlabeled Discs with Optimality Guarantees
• New perspective on sampling-based motion planning via random geometric graphs
• Simple Curve Embedding
• Map Matching with Simplicity Constraints