Dynamic well-separated pair decomposition made easy

John Fischer, Sariel Har-Peled

Research output: Contribution to conferencePaperpeer-review

Abstract

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)
Pages235-238
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

Conference

Conference17th Canadian Conference on Computational Geometry, CCCG 2005
CountryCanada
CityWindsor
Period8/10/058/12/05

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