Dynamic well-separated pair decomposition made easy

John Fischer, Sariel Har-Peled

Research output: Contribution to conferencePaperpeer-review


We focus on making compressed quadtrees, particularly those used in the implementation of well-separated pair decomposition, into effective dynamic data structures. We use random shifting to achieve logarithmic insertion and deletion time per pair with high probability.

Original languageEnglish (US)
Number of pages4
StatePublished - Jan 1 2005
Externally publishedYes
Event17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada
Duration: Aug 10 2005Aug 12 2005


Conference17th Canadian Conference on Computational Geometry, CCCG 2005

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Dynamic well-separated pair decomposition made easy'. Together they form a unique fingerprint.

Cite this