Geodesic Fréchet Distance Inside a Simple Polygon

Authors Carola Wenk, Atlas F. Cook



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1330.pdf
  • Filesize: 203 kB
  • 12 pages

Document Identifiers

Author Details

Carola Wenk
Atlas F. Cook

Cite AsGet BibTex

Carola Wenk and Atlas F. Cook. Geodesic Fréchet Distance Inside a Simple Polygon. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 193-204, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1330

Abstract

We unveil an alluring alternative to parametric search that applies to both the non-geodesic and geodesic Fr{'\e}chet optimization problems. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance and practical efficiency when compared to parametric search. We present the first algorithm for the geodesic Fr{'\e}chet distance between two polygonal curves $A$ and $B$ inside a simple bounding polygon $P$. The geodesic Fr{'\e}chet decision problem is solved almost as fast as its non-geodesic sibling and requires $O(N^{2log k)$ time and $O(k+N)$ space after $O(k)$ preprocessing, where $N$ is the larger of the complexities of $A$ and $B$ and $k$ is the complexity of $P$. The geodesic Fr{'\e}chet optimization problem is solved by a randomized approach in $O(k+N^{2log kNlog N)$ expected time and $O(k+N^{2)$ space. This runtime is only a logarithmic factor larger than the standard non-geodesic Fr{'\e}chet algorithm (Alt and Godau 1995). Results are also presented for the geodesic Fr{'\e}chet distance in a polygonal domain with obstacles and the geodesic Hausdorff distance for sets of points or sets of line segments inside a simple polygon $P$.
Keywords
  • Fréchet Distance
  • Geodesic
  • Parametric Search
  • Simple Polygon

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail