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

@misc{citeulike:102630, abstract = {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.}, archivePrefix = {arXiv}, author = {Har-Peled, Sariel and Mendel, Manor}, citeulike-article-id = {102630}, citeulike-linkout-0 = {http://arxiv.org/abs/cs.DS/0409057}, citeulike-linkout-1 = {http://arxiv.org/pdf/cs.DS/0409057}, day = {29}, eprint = {cs.DS/0409057}, keywords = {approximation, dimension, doubling, embedding, geometry}, month = {September}, posted-at = {2005-02-24 07:45:06}, priority = {4}, title = {Fast Construction of Nets in Low Dimensional Metrics, and Their Applications}, url = {http://arxiv.org/abs/cs.DS/0409057}, year = {2004} }

TY - ELEC ID - citeulike:102630 L3 - citeulike-article-id:102630 N2 - 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. TI - Fast Construction of Nets in Low Dimensional Metrics, and Their Applications KW - approximation KW - dimension KW - doubling KW - embedding KW - geometry AU - Har-Peled, Sariel AU - Mendel, Manor PY - 2004/09/29/ UR - http://arxiv.org/abs/cs.DS/0409057 ER -