2026-07-24T02:45:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24503 2025-12-16T14:00:04Z ddc:004 open_access

The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon van der Horst, Thijs van Kreveld, Marc Ophelders, Tim Speckmann, Bettina Fréchet distance approximation geodesic simple polygon The Fréchet distance is a popular similarity measure that is well-understood for polygonal curves in ℝ^d: near-quadratic time algorithms exist, and conditional lower bounds suggest that these results cannot be improved significantly, even in one dimension and when approximating with a factor less than three. We consider the special case where the curves bound a simple polygon and distances are measured via geodesics inside this simple polygon. Here the conditional lower bounds do not apply; Efrat et al. (2002) were able to give a near-linear time 2-approximation algorithm. In this paper, we significantly improve upon their result: we present a (1+ε)-approximation algorithm, for any ε > 0, that runs in 𝒪(1/(ε) (n+m log n) log nm log 1/(ε)) time for a simple polygon bounded by two curves with n and m vertices, respectively. To do so, we show how to compute the reachability of specific groups of points in the free space at once, by interpreting the free space as one between separated one-dimensional curves. We solve this one-dimensional problem in near-linear time, generalizing a result by Bringmann and Künnemann (2015). Finally, we give a linear time exact algorithm if the two curves bound a convex polygon. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thijs van der Horst and Marc van Kreveld and Tim Ophelders and Bettina Speckmann 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.35 urn:nbn:de:0030-drops-245038 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.35 eng https://creativecommons.org/licenses/by/4.0/legalcode