License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.76
URN: urn:nbn:de:0030-drops-64179
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6417/
Go to the corresponding LIPIcs Volume Portal

Solovey, Kiril ; Halperin, Dan

Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching

pdf-format:
LIPIcs-ESA-2016-76.pdf (0.6 MB)

Abstract

We describe a general probabilistic framework to address a variety of Fréchet-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.

BibTeX - Entry

@InProceedings{solovey_et_al:LIPIcs:2016:6417,
  author =	{Kiril Solovey and Dan Halperin},
  title =	{{Sampling-Based Bottleneck Pathfinding with Applications to Fr{\'e}chet Matching}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{76:1--76:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6417},
  URN =		{urn:nbn:de:0030-drops-64179},
  doi =		{10.4230/LIPIcs.ESA.2016.76},
  annote =	{Keywords: Computational geometry, Fr{\'e}chet distances, sampling-based algorithms, random geometric graphs, bottleneck pathfinding}
}

Keywords: Computational geometry, Fréchet distances, sampling-based algorithms, random geometric graphs, bottleneck pathfinding
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI