2 Search Results for "Huang, Haoqiang"

Document
DOI: 10.4230/LIPIcs.ESA.2024.28
A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case

Authors: Lotte Blank and Anne Driemel

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
The fine-grained complexity of computing the {Fréchet distance } has been a topic of much recent work, starting with the quadratic SETH-based conditional lower bound by Bringmann from 2014. Subsequent work established largely the same complexity lower bounds for the {Fréchet distance } in 1D. However, the imbalanced case, which was shown by Bringmann to be tight in dimensions d ≥ 2, was still left open. Filling in this gap, we show that a faster algorithm for the {Fréchet distance } in the imbalanced case is possible: Given two 1-dimensional curves of complexity n and n^{α} for some α ∈ (0,1), we can compute their {Fréchet distance } in O(n^{2α} log² n + n log n) time. This rules out a conditional lower bound of the form O((nm)^{1-ε}) that Bringmann showed for d ≥ 2 and any ε > 0 in turn showing a strict separation with the setting d = 1. At the heart of our approach lies a data structure that stores a 1-dimensional curve P of complexity n, and supports queries with a curve Q of complexity m for the continuous {Fréchet distance } between P and Q. The data structure has size in 𝒪(nlog n) and uses query time in 𝒪(m² log² n). Our proof uses a key lemma that is based on the concept of visiting orders and may be of independent interest. We demonstrate this by substantially simplifying the correctness proof of a clustering algorithm by Driemel, Krivošija and Sohler from 2015.
Cite as

Lotte Blank and Anne Driemel. A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blank_et_al:LIPIcs.ESA.2024.28,
  author =	{Blank, Lotte and Driemel, Anne},
  title =	{{A Faster Algorithm for the Fr\'{e}chet Distance in 1D for the Imbalanced Case}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.28},
  URN =		{urn:nbn:de:0030-drops-210999},
  doi =		{10.4230/LIPIcs.ESA.2024.28},
  annote =	{Keywords: \{Fr\'{e}chet distance\}, distance oracle, data structures, time series}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.40
Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance

Authors: Siu-Wing Cheng and Haoqiang Huang

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We propose κ-approximate nearest neighbor (ANN) data structures for n polygonal curves under the Fréchet distance in ℝ^d, where κ ∈ {1+ε,3+ε} and d ≥ 2. We assume that every input curve has at most m vertices, every query curve has at most k vertices, k ≪ m, and k is given for preprocessing. The query times are Õ(k(mn)^{0.5+ε}/ε^d+ k(d/ε)^O(dk)) for (1+ε)-ANN and Õ(k(mn)^{0.5+ε}/ε^d) for (3+ε)-ANN. The space and expected preprocessing time are Õ(k(mnd^d/ε^d)^O(k+1/ε²)) in both cases. In two and three dimensions, we improve the query times to O(1/ε)^O(k) ⋅ Õ(k) for (1+ε)-ANN and Õ(k) for (3+ε)-ANN. The space and expected preprocessing time improve to O(mn/ε)^O(k) ⋅ Õ(k) in both cases. For ease of presentation, we treat factors in our bounds that depend purely on d as O(1). The hidden polylog factors in the big-Õ notation have powers dependent on d.
Cite as

Siu-Wing Cheng and Haoqiang Huang. Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2023.40,
  author =	{Cheng, Siu-Wing and Huang, Haoqiang},
  title =	{{Approximate Nearest Neighbor for Polygonal Curves Under Fr\'{e}chet Distance}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.40},
  URN =		{urn:nbn:de:0030-drops-180929},
  doi =		{10.4230/LIPIcs.ICALP.2023.40},
  annote =	{Keywords: Polygonal curves, Fr\'{e}chet distance, approximate nearest neighbor}
}
  • Refine by Author
  • 1 Blank, Lotte
  • 1 Cheng, Siu-Wing
  • 1 Driemel, Anne
  • 1 Huang, Haoqiang

  • Refine by Classification
  • 2 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Fréchet distance
  • 1 Polygonal curves
  • 1 approximate nearest neighbor
  • 1 data structures
  • 1 distance oracle
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2023
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact