rapid-communication

Spanners under the Hausdorff and Fréchet distances

Authors:

Tsuri Farhana,

Matthew J. KatzAuthors Info & Claims

Volume 187, Issue C

https://doi.org/10.1016/j.ipl.2024.106513

Published: 18 October 2024 Publication History

Abstract

We initiate the study of spanners under the Hausdorff and Fréchet distances. Let S be a set of points in R d and ε a non-negative real number. A subgraph H of the Euclidean graph over S is an ε-Hausdorff-spanner (resp., an ε-Fréchet-spanner) of S, if for any two points u, v ∈ S there exists a path P ( u, v ) in H between u and v, such that the Hausdorff distance (resp., the Fréchet distance) between P ( u, v ) and u v ‾ is at most ε. We show that any t-spanner of a planar point-set S is a t 2 − 1 2-Hausdorff-spanner and a min ⁡ { t 2, 5 t 2 − 2 t − 3 4 }-Fréchet spanner. We also prove that for any t > 1, there exist a set of points S and an ε 1-Hausdorff-spanner of S and an ε 2-Fréchet-spanner of S, where ε 1 and ε 2 are constants, such that neither of them is a t-spanner.

Highlights

•

We initiate the study of spanners under the Hausdorff and Fréchet distances.

•

We show that any t-spanner of a planar point-set S is a f(t)-Hausdorff-spanner and a g(t)-Fréchet spanner.

•

We prove that for any t > 1, there exist a set of points S and an ε 1-Hausdorff-spanner of S that is not a t-spanner, where ε 1 is a constant.

•

We prove that for any t > 1, there exist a set of points S and an ε 2-Fréchet-spanner of S that is not a t-spanner, where ε 2 is a constant.

References

[1]

Sujoy Bhore, Csaba D. Tóth, Euclidean Steiner spanners: light and sparse, SIAM J. Discrete Math. 36 (3) (2022) 2411–2444.

Google Scholar

[2]

Paul B. Callahan, S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, J. ACM 42 (1) (1995) 67–90.

Digital Library

Google Scholar

[3]

Thomas Eiter, Heikki Mannila, Computing discrete Fréchet distance, Technical Report CD-TR 94/64 Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994.

Google Scholar

[4]

Maurice Fréchet, Sur quelques points du calcul fonctionnel, Rend. Circ. Mat. Palermo 22 (1906) 1–72.

Google Scholar

[5]

Felix Hausdorff, Grundzüge der Mengenlehre, Veit & Comp., 1914.

Google Scholar

[6]

Helge von Koch, Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire, Ark. Mat. Astron. Fys. 1 (1904) 681–704.

Google Scholar

[7]

Giri Narasimhan, Michiel Smid, Geometric Spanner Networks, Cambridge University Press, 2009.

Google Scholar

Index Terms

Spanners under the Hausdorff and Fréchet distances
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Index terms have been assigned to the content through auto-classification.

Recommendations

Angle-constrained spanners with angle at least /3

Let S be a set of n points in Rd and let t1 be a real number. A geometric graph G with vertex set S is called a t-spanner for S if for each two points p and q in S, there exists a path Q in G between p and q whose length is at most t times |pq|, the ...
Partial matching between surfaces using fréchet distance
SWAT'12: Proceedings of the 13th Scandinavian conference on Algorithm Theory

Computing the Fréchet distance for surfaces is a surprisingly hard problem. We introduce a partial variant of the Fréchet distance problem, which for given surfaces P and Q asks to compute a surface R⊆Q with minimum Fréchet distance to P. Like the ...
Fast fréchet distance between curves with long edges
IWISC '18: Proceedings of the 3rd International Workshop on Interactive and Spatial Computing

Computing Fréchet distance between two curves takes roughly quadratic time. The only strongly subquadratic time algorithm has been proposed in [7] for c-packed curves. In this paper, we show that for curves with long edges the Fréchet distance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 187, Issue C

Jan 2025

115 pages

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 18 October 2024

Author Tags

Qualifiers

Rapid-communication

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Highlights

References

Index Terms

Recommendations

Angle-constrained spanners with angle at least /3

Partial matching between surfaces using fréchet distance

Fast fréchet distance between curves with long edges

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations