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 improved …
core.ac.uk
acm.org
sci-hub.se 
arxiv.org 参考文章(50)
Patrice Assouad, Plongements lipschitziens dans Rn ,(2003)
Jiří Matoušek, Using the Borsuk-Ulam Theorem ,(2003)
Sariel Har-Peled, Soham Mazumdar, Coresets for $k$-Means and $k$-Median Clustering and their Applications. arXiv: Computational Geometry. ,(2018)
Juha Heinonen, Lectures on Analysis on Metric Spaces ,(2011)
Joram Lindenstrauss, Yoav Benyamini, Geometric Nonlinear Functional Analysis ,(1999)
Jouni Luukkainen, Eero Saksman, Every complete doubling metric space carries a doubling measure Proceedings of the American Mathematical Society. ,vol. 126, pp. 531- 534 ,(1998) , 10.1090/S0002-9939-98-04201-4
Jang-Mei Wu, Hausdorff dimension and doubling measures on metric spaces Proceedings of the American Mathematical Society. ,vol. 126, pp. 1453- 1459 ,(1998) , 10.1090/S0002-9939-98-04317-2
David Peleg, Informative Labeling Schemes for Graphs mathematical foundations of computer science. ,vol. 340, pp. 579- 588 ,(2000) , 10.1016/J.TCS.2005.03.015
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid, Approximate Distance Oracles Revisited Algorithms and Computation. ,vol. 2518, pp. 357- 368 ,(2002) , 10.1007/3-540-36136-7_32
John Kubiatowicz, Satish Rao, Sean Ma, Kirsten Hildrum, A note on the nearest neighbor in growth-restricted metrics symposium on discrete algorithms. pp. 560- 561 ,(2004) , 10.5555/982792.982874