June 2020 (v1)
Journal article
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...
Uploaded on: December 4, 2022