TY - CONF
T1 - Fast construction of nets in low dimensional metrics, and their applications
AU - Har-Peled, Sariel
AU - Mendel, Manor
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2005
Y1 - 2005
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, spanner construction, 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.
AB - 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, spanner construction, 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.
KW - Approximate distance oracle
KW - Approximate nearest neighbor search
KW - Compact representation scheme
KW - Doubling metrics
KW - Spanners
KW - Well separated pair decomposition
UR - http://www.scopus.com/inward/record.url?scp=33244493557&partnerID=8YFLogxK
U2 - 10.1145/1064092.1064117
DO - 10.1145/1064092.1064117
M3 - ???researchoutput.researchoutputtypes.contributiontoconference.paper???
AN - SCOPUS:33244493557
SP - 150
EP - 158
T2 - 21st Annual Symposium on Computational Geometry, SCG'05
Y2 - 6 June 2005 through 8 June 2005
ER -