2026-07-23T07:42:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24268 2025-11-12T13:39:39Z ddc:004 open_access

A Near-Linear Time Exact Algorithm for the L₁-Geodesic Fréchet Distance Between Two Curves on the Boundary of a Simple Polygon van der Horst, Thijs van Kreveld, Marc Ophelders, Tim Speckmann, Bettina Fréchet distance geodesic simple polygon Let P be a polygon with k vertices. Let R and B be two simple, interior disjoint curves on the boundary of P, with n and m vertices. We show how to compute the Fréchet distance between R and B using the geodesic L₁-distance in P in 𝒪(k log nm + (n+m) (log² nm log k + log⁴ nm)) time. 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 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.37 urn:nbn:de:0030-drops-242681 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.37 eng https://creativecommons.org/licenses/by/4.0/legalcode