Buchumschlag

Fréchet Distance in Subquadratic Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Cheng, Siu-Wing, Huang, Haoqiang
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Geometry Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
von: Cheng, Siu-Wing, et al.
Veröffentlicht: (2025)

Data Structures for Approximate Discrete Fréchet Distance
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2022)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
von: Ebbens, Matthijs, et al.
Veröffentlicht: (2024)

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

On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
von: Gudmundsson, Joachim, et al.
Veröffentlicht: (2022)

Relating Interleaving and Fréchet Distances via Ordered Merge Trees
von: Beurskens, Thijs, et al.
Veröffentlicht: (2023)

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

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

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

On computing the (exact) Fréchet distance with a frog
von: Conradi, Jacobus, et al.
Veröffentlicht: (2025)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
von: Mao, Xiao, et al.
Veröffentlicht: (2026)

Even Faster Algorithm for the Chamfer Distance
von: Feng, Ying, et al.
Veröffentlicht: (2025)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2023)

Improved Algorithms for Distance Selection and Related Problems
von: Wang, Haitao, et al.
Veröffentlicht: (2023)

On the Complexity of the Ordered Covering Problem in Distance Geometry
von: Souza, Michael, et al.
Veröffentlicht: (2025)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
von: Maus, Victor, et al.
Veröffentlicht: (2026)

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

Weakly Approximating Knapsack in Subquadratic Time
von: Chen, Lin, et al.
Veröffentlicht: (2025)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
von: Greenhut, Daniel, et al.
Veröffentlicht: (2025)

Optimal Orthogonal Drawings in Linear Time
von: Didimo, Walter, et al.
Veröffentlicht: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
von: Feng, Weiming, et al.
Veröffentlicht: (2024)

2-Layer Fan-Planarity in Polynomial Time
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2025)

Ortho-Radial Drawing in Near-Linear Time
von: Chang, Yi-Jun
Veröffentlicht: (2023)

Dynamically Maintaining the Persistent Homology of Time Series
von: di Montesano, Sebastiano Cultrera, et al.
Veröffentlicht: (2023)

Approximate Algorithms for Chamfer Distance Under Translation
von: Halevi, Gil, et al.
Veröffentlicht: (2026)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Incremental Planar Nearest Neighbor Queries with Optimal Query Time
von: Iacono, John, et al.
Veröffentlicht: (2025)

Continuous Map Matching to Paths under Travel Time Constraints
von: Bosch, Yannick, et al.
Veröffentlicht: (2025)

Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
von: Eppstein, David
Veröffentlicht: (2023)

A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance
von: Chambers, Erin Wolf, et al.
Veröffentlicht: (2024)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
von: S, Ajaykrishnan E, et al.
Veröffentlicht: (2025)

A Dynamic Working Set Method for Compressed Sensing
von: Cheng, Siu-Wing, et al.
Veröffentlicht: (2025)

Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
von: Cabello, Sergio, et al.
Veröffentlicht: (2021)

Space Complexity of Euclidean Clustering
von: Zhu, Xiaoyi, et al.
Veröffentlicht: (2024)

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

The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
von: Afshani, Peyman, et al.
Veröffentlicht: (2026)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
von: Chan, Timothy M., et al.
Veröffentlicht: (2025)

Algorithms for Distance Problems in Continuous Graphs
von: Cabello, Sergio, et al.
Veröffentlicht: (2025)

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
von: Huang, Lingxiao, et al.
Veröffentlicht: (2022)