High-Dimensional Approximate r-Nets

• Published in: Algorithmica 2020-06, Vol.82 (6), p.1675-1702
• Main Authors: Avarikioti, Z., Emiris, I. Z., Kavouras, L., Psarros, I.
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Clustering; Complexity; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Euclidean geometry; Geometry; Mathematics; Mathematics of Computing; Metric Geometry; Metric space; Polynomials; Software; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-019-00664-8

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. https://doi.org/10.1145/2728167 ) 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.