CaltechAUTHORS
  A Caltech Library Service

Fast construction of nets in low dimensional metrics, and their applications

Har-Peled, Sariel and Mendel, Manor (2005) Fast construction of nets in low dimensional metrics, and their applications. In: SCG '05 Proceedings of the twenty-first annual symposium on Computational geometry. ACM , New York, NY, pp. 150-158. ISBN 1-58113-991-8. https://resolver.caltech.edu/CaltechAUTHORS:20161102-162743403

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161102-162743403

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, 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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/0.1145/1064092.1064117DOIArticle
http://dl.acm.org/citation.cfm?doid=1064092.1064117PublisherArticle
Additional Information:© 2005 ACM. Work on this paper was partially supported by a NSF CAREER award CCR-0132901.
Funders:
Funding AgencyGrant Number
NSFCCR-0132901
Subject Keywords:Algorithms, Theory, Doubling metrics, approximate nearest neighbor search, compact representation scheme, approximate distance oracle, well separated pair decomposition, spanners
Classification Code:E.1 [ Data Structures ]: Trees, Distributed data structures; F.2.2 [ Analysis of algorithms and problem complexity ]: Geometrical problems and computations
Record Number:CaltechAUTHORS:20161102-162743403
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20161102-162743403
Official Citation:Sariel Har-Peled and Manor Mendel. 2005. Fast construction of nets in low dimensional metrics, and their applications. In Proceedings of the twenty-first annual symposium on Computational geometry (SCG '05). ACM, New York, NY, USA, 150-158. DOI=http://dx.doi.org/10.1145/1064092.1064117
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71698
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:02 Nov 2016 23:41
Last Modified:03 Oct 2019 16:10

Repository Staff Only: item control page