Fast Construction of Nets in Low Dimensional
Metrics, and Their Applications

Sariel Har-Peled
and
Manor Mendel.

We present a near linear time algorithm for constructing
hierarchical nets for a finite metric space with low doubling
dimension. As an applications of this, we show how one can
construct well-separated pairs decomposition of such a space with
linear number of pairs. Furthermore, we show how one can
construct, in near linear time, a data-structure of near linear
size, for answering approximate nearest neighbor queries in
polylogarithmic time. This improves several recent results on
those problems.

SoCG 05 talk slides.
slides source.
Man-Cho Anthony So read the paper carefully and figured out some
missing details about how to maintain the friends list. Here is his
writeup. Thanks Anthony!

@string{SICOMP = "SIAM J. Comput."}
@Article{hm-fcnld-06,
author = {S. {Har-Peled} and M. Mendel},
title = {Fast Construction of Nets in Low Dimensional
Metrics, and Their Applications},
journal = SICOMP,
year = 2006,
volume = 35,
number = 5,
pages = {1148--1184}
}