Fast construction of nets in low dimensional metrics, and their applications

DOI10.1145/1064092.1064117zbMath1380.68147arXivcs/0409057OpenAlexW1994772769MaRDI QIDQ5370607

Manor Mendel, Sariel Har-Peled

Publication date: 20 October 2017

Published in: Proceedings of the twenty-first annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0409057

zbMATH Keywords

spannersdoubling metricswell-separated pair decompositionapproximate distance oracleapproximate nearest neighbor searchcompact representation scheme

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Approximation algorithms (68W25)

Related Items (7)

New Doubling Spanners: Better and Simpler ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1 ⋮ High-dimensional approximate \(r\)-nets ⋮ Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree ⋮ Unnamed Item ⋮ Self-organizing flows in social networks

This page was built for publication: Fast construction of nets in low dimensional metrics, and their applications