Cover Image

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cheng, Siu-Wing, Huang, Haoqiang, Zhang, Shuo
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fréchet Distance in Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2024)

Data Structures for Approximate Discrete Fréchet Distance
by: van der Hoog, Ivor, et al.
Published: (2022)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
by: Mao, Xiao, et al.
Published: (2026)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
by: Gudmundsson, Joachim, et al.
Published: (2022)

Relating Interleaving and Fréchet Distances via Ordered Merge Trees
by: Beurskens, Thijs, et al.
Published: (2023)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
by: Conradi, Jacobus, et al.
Published: (2026)

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
by: Park, Seongbin, et al.
Published: (2026)

Approximate Distance Sensitivity Oracles in Subquadratic Space
by: Bilò, Davide, et al.
Published: (2023)

On computing the (exact) Fréchet distance with a frog
by: Conradi, Jacobus, et al.
Published: (2025)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

Weakly Approximating Knapsack in Subquadratic Time
by: Chen, Lin, et al.
Published: (2025)

Approximate Algorithms for Chamfer Distance Under Translation
by: Halevi, Gil, et al.
Published: (2026)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Distance Approximating Minors for Planar and Minor-Free Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
by: Bathie, Gabriel, et al.
Published: (2025)

On Strong Diameter Padded Decompositions
by: Filtser, Arnold
Published: (2019)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
by: Bilò, Davide, et al.
Published: (2024)

On the Complexity of the Ordered Covering Problem in Distance Geometry
by: Souza, Michael, et al.
Published: (2025)

Improved Algorithms for Distance Selection and Related Problems
by: Wang, Haitao, et al.
Published: (2023)

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

Approximately: Independence Implies Vertex Cover
by: Har-Peled, Sariel
Published: (2023)

On Approximating the Weighted Region Problem in Square Tessellations
by: Kakimura, Naonori, et al.
Published: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
by: Maus, Victor, et al.
Published: (2026)

Improved Approximation Algorithms for Three-Dimensional Bin Packing
by: Kar, Debajyoti, et al.
Published: (2025)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
by: Kar, Debajyoti, et al.
Published: (2026)

An Improved FPT Algorithm for Computing the Interleaving Distance between Merge Trees via Path-Preserving Maps
by: P V, Althaf, et al.
Published: (2026)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)