CS Paper Radar

Shaving Two Logs for Discrete and Continuous Fréchet Distance

Timothy M Chan, Isaac M Hair

cs.CG ·submitted 2026-10-12 08:14 UTC · v1

Abstract

We revisit the classical computational geometry problem of computing the exact (discrete or continuous) Fréchet distance between two given polygonal curves with $n$ vertices in a constant dimension $d$. 1. We present an $O((n^2/\log^2n)\log^2\log n)$-time deterministic algorithm for the discrete Fréchet distance problem, improving the previous $O((n^2/\log n)\log\log n)$ result by Agarwal, Ben Avraham, Kaplan, and Sharir [SODA'13]. 2. We present an $O((n^2/\log^2n)\log^2\log n)$-time deterministic algorithm for the decision version of the continuous Fréchet distance problem, improving the previous $O((n^2/\log n)\log^2\log n)$ result by Buchin, Buchin, Meulemans, and Mulzer [SODA'14] and the recent $O(n^2/\log^{1+μ}n)$ randomized result by Cheng and Huang [SODA'25] for a small unspecified constant $μ>0$ (which converges to 0 as $d$ increases). 3. Finally, we present an $O((n^2/\log^2 n)\log^{O(1)}\log n)$-time Las Vegas randomized algorithm for the continuous Fréchet distance problem, improving the previous $O(n^2\log^2\log n)$ randomized result by Buchin, Buchin, Meulemans, and Mulzer [SODA'14] and the recent $O(n^2/\log^μn)$-time randomized result claimed by Cheng and Huang [SODA'25]. Since these problems have near-quadratic OV-based conditional lower bounds and shaving of two log factors is the best that is known for similar, simpler problems such as longest common subsequence and edit distance, our results reach the natural limit of the current state of the art (up to $\log\log$ factors).

Closest papers

Nearest neighbours by meaning across the whole index.

Constant Approximation of Fréchet Distance in Near-Linear Time

cs.CG ·2026-10-30 ·Haoqiang Huang, Zihe Wang, Shuo Zhang
similarity 0.75
Abstract

We give the first constant-factor approximation for the Fréchet distance in near-linear time. Given two polygonal curves in $\mathbb{R}^d$ with $n$ and $m$ vertices, respectively, where $m\le n$, our deterministic algorithm runs in $O(n^{1+\varepsilon})$ time for every fixed $\varepsilon>0$ and $d$, with an approximation factor depending only on $\varepsilon$ and $d$. The same result holds for the discrete Fréchet distance. Our result extends the line of work initiated by Cheng, Huang, and Zhang (STOC 2025) from strongly subquadratic to near-linear time. Our algorithm recursively balances preprocessing and query time. An index for comparing subcurves of a single curve supports faster queries between different curves. We obtain this speedup by replacing one curve with surrogates assembled from indexed subcurves of the other and shared across starting points of matchings. Faster queries then reduce the cost of building the next index. Compact boundary reachability summaries allow the answers to be reused in later recursive calls. After a number of rounds depending only on $\varepsilon$, both preprocessing and query time are near-linear.

0.15

A Dimension-Reducing Fréchet Simplification Oracle

cs.CG ·2026-08-31 ·Boris Aronov, Tsuri Farhana, Matthew J. Katz, Indu Ramesh
published similarity 0.69
Abstract · 21 pages, 1 figure

Let $P$ be a polygonal curve with $n$ vertices in the plane. We construct a data structure of size $O(n \log n)$ suited for simplification queries of the following kind. Given a query line $\ell$ and an integer $k\ge1$, find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to $P$, among all such curves. Using our data structure, a query can be handled in $O(k^2 \log^3 n + k\log^4 n)$ time. More generally, a geometric tree $T$ on $n$ vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair $u$, $v$ of its vertices, a line $\ell$, and an integer $k\ge1$, one can find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to the path from $u$ to $v$ in $T$, in time $O(k^2 \mathop{polylog} n)$. For the general dimension-reduction problem, where $P$ is a curve in $\mathbb{R}^d$ ($d \ge 3$), $0 < \varepsilon_0 < 1$ is a real parameter, and a query specifies a $g$-flat $h$ ($1 \le g \le d-1$) and an integer $k \ge 1$, we construct a data structure of size $O(n\log n + f(\varepsilon_0) n)$, where $f(\varepsilon_0)=(1+1/\varepsilon_0)^{(d-1)/2}$, that allows us to find a curve $Q$ on $h$ with at most $k$ vertices, whose discrete Fréchet distance to $P$ is at most $1+\varepsilon_0$ times the distance of $Q^*$ to $P$, where $Q^*$ is such a curve that minimizes the distance to $P$. The query handling time is $O(f(\varepsilon_0) k^2 \log^2 n)$.

0.38

How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance

cs.DS cs.CG ·2026-10-21 ·Leonid Barenboim, Arnold Filtser, Omrit Filtser, Orr Fischer
similarity 0.69
Abstract

The Fréchet distance (also known as the dog-leash distance) is a well-studied and prevalent distance measure for polygonal curves. In this paper we present parallel algorithms for computing the discrete \frechet\ distance between two curves, in both the PRAM and MPC models. For two polygonal curves of length $n$, we show that the distance between them can be computed in the PRAM model in $O(\log n/ σ)$ rounds and $\tilde{O}(n^{2+σ})$ total work for any $0<σ<1$. In the sublinear MPC model with $n^ρ$ space per machine, it can be computed in $O(\log n / ρ^2)$ rounds and $\tilde{O}(n^{2+ρ})$ total space. For $c$-packed curves, we match our bounds to the sequential algorithms, showing that a $(1+\eps)$-approximation of the distance can be computed in the PRAM model in $O(\log{n}+1/σ^3)$ rounds and $\tilde{O}(n^{1+σ})$ total work, and in the sublinear MPC model in $O(1 /ρ^3)$ rounds and $\tilde{O}(n^{1+ρ})$ total space, for any constant $\eps>0$. As part of our algorithms for $c$-packed curves, we also present parallel algorithms for computing curve simplifications, which may be of independent interest.

0.17

Polynomial-time algorithm for exact $(1,2)$-center problem under continuous Fréchet distance

cs.CG cs.DS ·2026-09-30 ·Soumya Bhattacharya, Serene Rasheed, Sasanka Roy
similarity 0.68
Abstract

In this paper, we explore the $(1,2)$-center problem for polygonal curves under continuous Fréchet distance. The $(k,\ell)$-center problem, in general, is known to be NP-hard. Aronov, Filtser, Horton, Katz, and Sheikhan (WADS'19) gave a polynomial-time algorithm for the $(1,2)$-center of curves in the plane under the discrete Fréchet distance. To the best of our knowledge, the $(1,2)$-center under continuous Fréchet distance has not been studied yet. We present a polynomial time algorithm to solve the problem exactly under both $\mathbb{L}_2$ and $\mathbb{L}_\infty$ norm, running in $O\bigr((n^2r+nr^2)^{2+ε}\bigl)$ time for curves in the plane where $r$ is the number of input curves and $n$ is the maximum complexity of any curve. Further, for curves in any dimension $d$, the expected time to compute the center using the algorithm is $O\bigr((n^2r+nr^2)^{2(d-1)+ε}\bigl)$. We have also shown that an $(1+\widetildeε)-$factor approximation of $(1,2)$-center can be computed in $O(n^2r+nr^2+1/ε^s)$ time for any $ε>\widetildeε>0$ and some constant $s$ for curves in the plane. For curves in the plane, we have shown that, with the center restricted to be horizontal, we can compute the exact center in $O(n^2r+nr^2)$ time. An algorithm has been introduced to find a $3$-factor approximation of the $(1,2)$-center in time linear in the number of curves. A formulation was introduced by de Berg, Mehrabi, and Ophelders (CCCG'17) to measure Fréchet distance between a curve and a query segment under $\mathbb{L}_2$ norm for curves in the plane. We have shown the formulation is valid under both $\mathbb{L}_2$ and $\mathbb{L}_\infty$ norm for curves in $\mathbb{R}^d$.

0.22

Deterministic Distance Selection in $O(n^{4/3})$ Time

cs.CG cs.DS ·2026-10-07 ·Haitao Wang
top venue similarity 0.66
Abstract · To appear in SODA 2027

Let $P$ be a set of $n$ points in the plane. Given an integer $K$ with $1\le K\le {n\choose 2}$, the distance selection problem asks for the $K$-th smallest distance among all pairwise distances of the points of $P$. The problem has been studied extensively over the past four decades. Recently, Chan and Zheng (2023) gave a randomized algorithm with $O(n^{4/3})$ expected running time, while the best known deterministic algorithm runs in $O(n^{4/3}\log n)$ time. In this paper, we present a deterministic $O(n^{4/3})$-time algorithm for the problem, matching the best known randomized complexity. We also consider the more general bichromatic version of the problem, where two point sets $A$ and $B$ are given, with $m=|A|$ and $n=|B|$, and the goal is to find the $K$-th smallest distance among the $mn$ distances between points of $A$ and points of $B$. For this problem, the best previously known algorithm runs in $O((m\log n+n\log m+m^{2/3}n^{2/3})\log(m+n))$ time. We present a new deterministic algorithm with running time $O(m\log^2 n+n\log^2 m+m^{2/3}n^{2/3})$.

0.41

Optimal Planar $k$ Nearest Neighbors Queries for Additively Weighted Euclidean Distances and Convex Metrics

cs.CG ·2026-10-12 ·Chih-Hung Liu
top venuetheory similarity 0.66
Abstract · 78 pages. A conference version will appear in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.

0.42

Fast Geometric Spanners via Approximate Nearest Neighbor Search

cs.DS cs.CG ·2026-09-22 ·Alexandr Andoni, Manuel Paez, Krish Singal, Tian Zhang
similarity 0.64
Abstract

We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neighbor search. In particular, we show the following results for any metric space $\mathsf{M} = ([n], \mathsf{d})$ with aspect ratio $Δ$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime $τ_{\mathsf{M}}(n)$, (1) There exists an algorithm that, for any $k \in \mathbb{N}$, constructs an $O(c k)$-distortion spanner with $\tilde{O}(kn^{1+1/2k} \log Δ)$ edges and runs in time $\tilde{O}(τ_{\mathsf{M}} \cdot k n^{1/k} \log Δ)$. (2) Any algorithm that learns at most $o(n^{1+1/k}/k)$ pairwise distances by querying a distance oracle and a blackbox batch nearest neighbor search oracle necessarily incurs $Ω(c k)$ distortion. Our results entail that (truly) sub-quadratic time algorithms for spanner construction is equivalent to subquadratic time BANN (up to constant-factor losses). As a further application, we use our fast spanner constructions to obtain a fast algorithm for approximating the Wasserstein distance $\mathsf{W}_q$, for all $q > 1$, over any metric space admitting an efficient batch approximate nearest neighbor search algorithm. Together with recent new efficient algorithms for approximate nearest neighbor search in $\ell_p$ spaces, for $p > 2$, our results entail the first subquadratic time algorithms for spanner construction (with the stated size-distortion tradeoff) and $\mathsf{W}_q$ distance approximation over these metric spaces.

0.07

Finding the Farthest in High Dimensions: Dynamic Diameter and Farthest-Neighbor Search

cs.DS ·2026-11-12 ·Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.63
Abstract

We give algorithms for maintaining diameter in the dynamic model, and for answering farthest-neighbor queries on a fixed point set, in high-dimensional Euclidean space. For every fixed $1<c<\sqrt2$, update horizon $t$, and error probability $δ$, we maintain an actual factor-$c$ diameter pair with worst-case update time $n^{2/c^2-1}\text{poly}_c(d,\log(2nt/δ))$ and space $n^{2/c^2}\text{poly}_c(d,\log(2nt/δ))$. Here $n$ bounds the number of active point identities. The update exponent improves Indyk's SODA~2003 bound from $1/c^2$ to $2/c^2-1$, while the space exponent improves from $1+1/c^2$ to $2/c^2$. At $c=\sqrt{3/2}$, the update exponent decreases from $2/3$ to $1/3$. A separate construction achieves approximation exactly $\sqrt2$ with update time polynomial in $d$ and $\log(2nt/δ)$. With probability at least $1-δ$, every maintained answer during the first $t$ updates is correct, even when updates depend on all previous answers and random choices. A second construction improves the update exponent when the space exponent is close to one. On rational inputs, it has an always-correct variant with expected amortized update bounds over every fixed finite prefix of an adaptive execution, without an advance update horizon. The dynamic structures store a current answer, so reporting its two point identifiers takes constant time. The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation $\sqrt2-\varepsilon$, the diameter time is $n^{1+O(\varepsilon)}$, and the query time is $n^{O(\varepsilon)+o(1)}$ with near-linear preprocessing and space, up to polynomial input-parameter factors.

0.25