Fast Construction of Nets in Low Dimensional Metrics, and Their Applications
<|reference_start|>Fast Construction of Nets in Low Dimensional Metrics, and Their Applications: 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 improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.<|reference_end|>
@article{har-peled2004fast,
    title={Fast Construction of Nets in Low Dimensional Metrics, and Their
  Applications},
    author={Sariel Har-Peled, Manor Mendel},
    journal={SIAM J. Comput. 35(5):1148-1184, 2006},
    year={2004},
    doi={10.1137/S0097539704446281},
    archivePrefix={arXiv},
    eprint={cs/0409057},
    primaryClass={cs.DS cs.CG}
}