DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.69

Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

Authors: Joost van der Laan, Frank Staals, and Lorenzo Theunissen

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

We present efficient data structures for approximate nearest neighbor searching and approximate 2-point shortest path queries in a two-dimensional polygonal domain P with n vertices. Our goal is to store a dynamic set of m point sites S in P so that we can efficiently find a site s ∈ S closest to an arbitrary query point q. We will allow both insertions and deletions in the set of sites S. However, as even just computing the distance between an arbitrary pair of points q,s ∈ P requires a substantial amount of space, we allow for approximating the distances. Given a parameter ε > 0, we build an O(n/(ε)log n) space data structure that can compute a 1+ε-approximation of the distance between q and s in O((1/ε²)log n) time. Building on this, we then obtain an O((n+m)/ε log n + m/ε log m) space data structure that allows us to report a site s ∈ S so that the distance between query point q and s is at most (1+ε)-times the distance between q and its true nearest neighbor in O((1/ε²)log n + 1/(ε)log n log m + (1/ε)log² m) time. Our data structure supports updates in O((1/ε²)log n + (1/ε)log n log m + (1/ε)log² m) amortized time.

Cite as

Joost van der Laan, Frank Staals, and Lorenzo Theunissen. Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 69:1-69:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{vanderlaan_et_al:LIPIcs.SoCG.2026.69,
  author =	{van der Laan, Joost and Staals, Frank and Theunissen, Lorenzo},
  title =	{{Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{69:1--69:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.69},
  URN =		{urn:nbn:de:0030-drops-258769},
  doi =		{10.4230/LIPIcs.SoCG.2026.69},
  annote =	{Keywords: dynamic data structure, nearest neighbor search, polygonal domain}
}

Search Results

Documents authored by Theunissen, Lorenzo

Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

Abstract

Cite as

Thanks for your feedback!

Could not send message