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

Sariel Har-Peled, Manor Mendel

We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain i…