Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

DOI10.1145/2582112.2582161zbMath1395.68278OpenAlexW2063567013MaRDI QIDQ4635566

Timothy M. Chan, Sunil Arya

Publication date: 23 April 2018

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

Full work available at URL: https://doi.org/10.1145/2582112.2582161

zbMATH Keywords

minimum spanning treenearest neighborcoresetsbichromatic closest pair\(\varepsilon\)-dependencies

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (6)

Communication costs in a geometric communication network ⋮ Approximate Polytope Membership Queries ⋮ Unnamed Item ⋮ Approximate Convex Hull of Data Streams ⋮ Faster DBSCAN and HDBSCAN in Low-Dimensional Euclidean Spaces ⋮ Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces

This page was built for publication: Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels