Approximate Nearest Neighbor Search in Metrics of Planar Graphs

DOI10.4230/LIPIcs.APPROX-RANDOM.2015.20zbMath1375.68043OpenAlexW2285192099MaRDI QIDQ5351887

Shiri Chechik, Ittai Abraham, Udi Wieder, Robert Krauthgamer

Publication date: 31 August 2017

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.20

zbMATH Keywords

planar graphsdata structuresnearest neighbor searchplanar separatorplanar metrics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items

Metric Embedding via Shortest Path Decompositions ⋮ The nearest colored node in a tree ⋮ Succinct data structures for nearest colored node in a tree ⋮ Efficient vertex-label distance oracles for planar graphs