A Subquadratic nε-approximation for the Continuous Fréchet Distance.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with m and n vertices in R^d in O(mn(log log n)²) time; doing so in strongly subquadratic time is a longstanding open problem. Recent conditional lower bounds suggest that it is unlikely that a strongly subquadratic algorithm exists. Moreover, it is unlikely that we can approximate the Fr ́echet distance to within a factor 3 in strongly subquadratic time, even if d = 1. The best current results establish a tradeoff between approximation quality and running time. Specifically, Colombe and Fox (SoCG, 2021) give an O(α)-approximate algorithm that runs in O((n3/α2) log n) time for any α ∈ [√n, n], assuming m = n. In this paper, we improve this result with an O(α)-approximate algorithm that runs in O((n + mn/α) log³ n) time for any α ∈ [1, n], assuming m ≤ n and
constant dimension d.
Originele taal-2Engels
TitelProc. 34th Annual Symposium on Discrete Algorithms (SODA)
Pagina's1759-1776
Aantal pagina's18
DOI's
StatusGepubliceerd - 2023
EvenementSymposium on Discrete Algorithms (SODA23) - Florence, Italië
Duur: 22 jan. 202325 jan. 2023

Congres

CongresSymposium on Discrete Algorithms (SODA23)
Verkorte titelSODA
Land/RegioItalië
StadFlorence
Periode22/01/2325/01/23

Bibliografische nota

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

Vingerafdruk

Duik in de onderzoeksthema's van 'A Subquadratic nε-approximation for the Continuous Fréchet Distance.'. Samen vormen ze een unieke vingerafdruk.

Citeer dit