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: |
| |||||||||
| Additional Information: | © 2005 ACM. Work on this paper was partially supported by a NSF CAREER award CCR-0132901. | |||||||||
| Funders: |
| |||||||||
| 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
