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