DROPS

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 Õ(k(mn)^{0.5+ε}/ε^d+ k(d/ε)^O(dk)) for (1+ε)-ANN and Õ(k(mn)^{0.5+ε}/ε^d) for (3+ε)-ANN. The space and expected preprocessing time are Õ(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) ⋅ Õ(k) for (1+ε)-ANN and Õ(k) for (3+ε)-ANN. The space and expected preprocessing time improve to O(mn/ε)^O(k) ⋅ Õ(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-Õ 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}
}

Search Results

Documents authored by Huang, Haoqiang

Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance

Abstract

Cite as

Thanks for your feedback!

Could not send message