Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Lukas Kavouras Anonymously browsing from at 00:56:34, 24-05-2019. login

MSc thesis of Lukas Kavouras

High dimensional approximate r-nets

Supervisor: Ioannis Emiris

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.

Defended: Nov. 8, 2016.

Scientific committee


Download thesis.


Page updates

No recent updates.

Feeds RSS and Atom feeds

all posts RSS
news RSS
announcements RSS
website news RSS
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2019 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.