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

Sariel Har-Peled, Manor Mendel

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)1148-1184
Number of pages37
JournalSIAM Journal on Computing
Volume35
Issue number5
DOIs
StatePublished - 2006

Keywords

  • Approximate distance oracle
  • Distance labeling
  • Doubling dimension
  • Doubling measure
  • Metric nets
  • Nearest neighbor search
  • Quadtree

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

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