# High-dimensional approximate r-nets

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 \epsilon>0, the approximation factor is 1+\epsilon and the complexity is polynomial in the dimension and subquadratic in the number of points. The algorithm succeeds with high probability. More specifically, the best previously known LSH-based construction of Eppstein et al. [EHS15] is improved in terms of complexity by reducing the dependence on \epsilon, provided that $\epsilon$ is sufficiently small. Our method does not require LSH but, instead, follows Valiant's [Val15] 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+\epsilon)-approximate k-th nearest neighbor distance in time subquadratic in the size of the input.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [12 references]

https://hal.inria.fr/hal-01636792
Contributor : Ioannis Emiris <>
Submitted on : Wednesday, October 17, 2018 - 5:56:25 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Friday, January 18, 2019 - 3:51:33 PM

### File

EmirisEtalSoda1607.04755.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-01636792, version 1
• ARXIV : 1607.04755

### Citation

Georgia Avarikioti, Ioannis Z. Emiris, Loukas Kavouras, Ioannis Psarros. High-dimensional approximate r-nets. SODA: ACM/SIAM Symposium on Discrete Algorithms, Jan 2017, Barcelone, Spain. ⟨hal-01636792⟩

Record views