  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.\ \cite{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 \cite{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.
