Well-separated pair decomposition in linear time?

Research output: Contribution to journalArticlepeer-review


Given a point set in a fixed dimension, we note that a well-separated pair decomposition can be found in linear time if we assume that the ratio of the farthest pair distance to the closest pair distance is polynomially bounded. Many consequences follow; for example, we can construct spanners or solve the all-nearest-neighbors problem in linear time (under the same assumption), and we compute an approximate Euclidean minimum spanning tree in linear time (without any assumption).

Original languageEnglish (US)
Pages (from-to)138-141
Number of pages4
JournalInformation Processing Letters
Issue number5
StatePublished - Aug 16 2008
Externally publishedYes


  • Approximation algorithms
  • Computational geometry
  • Quadtrees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Well-separated pair decomposition in linear time?'. Together they form a unique fingerprint.

Cite this