Skip to Main content Skip to Navigation
Journal articles

High-Dimensional Approximate r-Nets

Zeta Avarikioti 1 Ioannis Z. Emiris 1, 2 Loukas Kavouras 1 Ioannis Psarros 1, 2
2 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , NKUA - National and Kapodistrian University of Athens
Abstract : The construction of r-nets offers a powerful tool in computational and metric geometry. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate r-nets with respect to Euclidean distance. For any fixed ϵ>0, the approximation factor is 1+ϵ and the complexity is polynomial in the dimension and subquadratic in the number of points; the algorithm succeeds with high probability. Specifically, we improve upon the best previously known (LSH-based) construction of Eppstein et al. (Approximate greedy clustering and distance selection for graph metrics, 2015. CoRR arxiv: abs/1507.01555) in terms of complexity, by reducing the dependence on ϵ, provided that ϵ is sufficiently small. Moreover, our method does not require LSH but follows Valiant’s (J ACM 62(2):13, 2015. approach in designing a sequence of reductions of our problem to other problems in different spaces, under Euclidean distance or inner product, for which r-nets are computed efficiently and the error can be controlled. Our result immediately implies efficient solutions to a number of geometric problems in high dimension, such as finding the (1+ϵ)-approximate k-th nearest neighbor distance in time subquadratic in the size of the input.
Document type :
Journal articles
Complete list of metadatas
Contributor : Ioannis Emiris <>
Submitted on : Monday, December 7, 2020 - 8:54:10 PM
Last modification on : Thursday, December 17, 2020 - 3:16:46 AM




Zeta Avarikioti, Ioannis Z. Emiris, Loukas Kavouras, Ioannis Psarros. High-Dimensional Approximate r-Nets. Algorithmica, Springer Verlag, 2020, 82 (6), pp.1675-1702. ⟨10.1007/s00453-019-00664-8⟩. ⟨hal-03045138⟩



Record views