A Near-Linear Time Exact Algorithm for the L1-Geodesic Fréchet Distance Between Two Curves on the Boundary of a Simple Polygon
| Title: | A Near-Linear Time Exact Algorithm for the L1-Geodesic Fréchet Distance Between Two Curves on the Boundary of a Simple Polygon |
|---|---|
| Authors: | van der Horst, Thijs; van Kreveld, Marc; Ophelders, Tim; Speckmann, Bettina; Sub Geometric Computing; Dep Informatica |
| Publication Year: | 2025 |
| Subject Terms: | Fréchet distance; geodesic; simple polygon; Software |
| Description: | 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 L1-distance in P in O(klog nm + (n + m)(log2 nmlog k + log4 nm)) time. |
| Document Type: | book part |
| File Description: | text/plain |
| Language: | English |
| Relation: | https://dspace.library.uu.nl/handle/1874/483170 |
| Availability: | https://dspace.library.uu.nl/handle/1874/483170 |
| Rights: | info:eu-repo/semantics/OpenAccess |
| Accession Number: | edsbas.550F74BD |
| Database: | BASE |