2026-07-26T16:45:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5292 2024-03-06T10:36:14Z ddc:004 open_access

Approximate Nearest Neighbor Search in Metrics of Planar Graphs Abraham, Ittai Chechik, Shiri Krauthgamer, Robert Wieder, Udi Data Structures Nearest Neighbor Search Planar Graphs Planar Metrics Planar Separator We investigate the problem of approximate Nearest-Neighbor Search (NNS) in graphical metrics: The task is to preprocess an edge-weighted graph G=(V,E) on m vertices and a small "dataset" D \subset V of size n << m, so that given a query point q \in V, one can quickly approximate dist(q,D) (the distance from q to its closest vertex in D) and find a vertex a \in D within this approximated distance. We assume the query algorithm has access to a distance oracle, that quickly evaluates the exact distance between any pair of vertices. For planar graphs G with maximum degree Delta, we show how to efficiently construct a compact data structure -- of size ~O(n(Delta+1/epsilon)) -- that answers (1+epsilon)-NNS queries in time ~O(Delta+1/epsilon). Thus, as far as NNS applications are concerned, metrics derived from bounded-degree planar graphs behave as low-dimensional metrics, even though planar metrics do not necessarily have a low doubling dimension, nor can they be embedded with low distortion into l_2. We complement our algorithmic result by lower bounds showing that the access to an exact distance oracle (rather than an approximate one) and the dependency on Delta (in query time) are both essential. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ittai Abraham and Shiri Chechik and Robert Krauthgamer and Udi Wieder 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.20 urn:nbn:de:0030-drops-52923 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.20 eng https://creativecommons.org/licenses/by/3.0/legalcode