2026-08-12T23:53:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1330 2024-03-06T10:32:58Z ddc:004 open_access

Geodesic Fréchet Distance Inside a Simple Polygon Wenk, Carola Cook, Atlas F. Fréchet Distance Geodesic Parametric Search Simple Polygon 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$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carola Wenk and Atlas F. Cook 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1330 urn:nbn:de:0030-drops-13303 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1330 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode