Cover Image

Computing the Fréchet Distance When Just One Curve is $c$-Packed: A Simple Almost-Tight Algorithm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Conradi, Jacobus, van der Hoog, Ivor, van der Horst, Thijs, Ophelders, Tim
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon
by: van der Horst, Thijs, et al.
Published: (2025)

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

Fréchet Distance in Unweighted Planar Graphs
by: van der Hoog, Ivor, et al.
Published: (2025)

Faster, Deterministic and Space Efficient Subtrajectory Clustering
by: van der Hoog, Ivor, et al.
Published: (2024)

Faster Fréchet Distance Approximation through Truncated Smoothing
by: van der Horst, Thijs, et al.
Published: (2024)

On the Discrete Fréchet Distance in a Graph
by: Driemel, Anne, et al.
Published: (2022)

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

Simpler and Faster Contiguous Art Gallery
by: de Berg, Sarita, et al.
Published: (2025)

A near-linear time exact algorithm for the $L_1$-geodesic Fréchet distance between two curves on the boundary of a simple polygon
by: van der Horst, Thijs, et al.
Published: (2025)

The Contiguous Art Gallery Problem is in Θ(n log n)
by: de Berg, Sarita, et al.
Published: (2025)

Barking dogs: A Fréchet distance variant for detour detection
by: van der Hoog, Ivor, et al.
Published: (2024)

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

Reconfiguration of Squares Using a Constant Number of Moves Each
by: van der Horst, Thijs, et al.
Published: (2026)

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)

A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)

Simpler is Faster: Practical Distance Reporting by Sorting Along a Space-Filling Curve
by: de Berg, Sarita, et al.
Published: (2025)

Computing Planar Convex Hulls with a Promise
by: Aghamolaei, Sepideh, et al.
Published: (2026)

Practical Insertion-Only Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)

Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D
by: Blank, Lotte, et al.
Published: (2025)

Engineering Fully Dynamic Convex Hulls
by: van der Hoog, Ivor, et al.
Published: (2026)

Revisiting the Fréchet distance between piecewise smooth curves
by: Conradi, Jacobus, et al.
Published: (2024)

Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs
by: van der Hoog, Ivor, et al.
Published: (2024)

Efficient Greedy Discrete Subtrajectory Clustering
by: van der Hoog, Ivor, et al.
Published: (2025)

Instance-Optimal Imprecise Convex Hull
by: de Berg, Sarita, et al.
Published: (2025)

Locally Correct Interleavings between Merge Trees
by: Beurskens, Thijs, et al.
Published: (2025)

Tight Bounds for Sorting Under Partial Information
by: van der Hoog, Ivor, et al.
Published: (2024)

$(1+\varepsilon)$-ANN Data Structure for Curves via Subspaces of Bounded Doubling Dimension
by: Conradi, Jacobus, et al.
Published: (2023)

Dynamic Indexing Through Learned Indices with Worst-case Guarantees
by: Gæde, Emil Toftegaard, et al.
Published: (2025)

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
by: de Berg, Sarita, et al.
Published: (2026)

Sweeping Orders for Simplicial Complex Reconstruction
by: Ophelders, Tim, et al.
Published: (2025)

Separator for $c$-Packed Segments and Curves
by: Har-Peled, Sariel
Published: (2026)

Computing Non-Obtuse Triangulations with Few Steiner Points
by: Abrahamsen, Mikkel, et al.
Published: (2025)

Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better
by: Conradi, Jacobus, et al.
Published: (2025)

The Presort Hierarchy for Geometric Problems
by: van der Hoog, Ivor, et al.
Published: (2026)

Finding Complex Patterns in Trajectory Data via Geometric Set Cover
by: Conradi, Jacobus, et al.
Published: (2023)

ParkView: Visualizing Monotone Interleavings
by: Beurskens, Thijs, et al.
Published: (2025)

Fréchet Edit Distance
by: Fox, Emily, et al.
Published: (2024)

Fast Approximations and Coresets for (k, l)-Median under Dynamic Time Warping
by: Conradi, Jacobus, et al.
Published: (2023)

Discrete Fréchet Distance Oracles
by: Aronov, Boris, et al.
Published: (2024)