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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1148-1184 |
| Number of pages | 37 |
| Journal | SIAM Journal on Computing |
| Volume | 35 |
| Issue number | 5 |
| DOIs | |
| State | Published - 2006 |
Keywords
- Approximate distance oracle
- Distance labeling
- Doubling dimension
- Doubling measure
- Metric nets
- Nearest neighbor search
- Quadtree
ASJC Scopus subject areas
- General Computer Science
- General Mathematics
Fingerprint
Dive into the research topics of 'Fast construction of nets in low-dimensional metrics and their applications'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS