20000101
I/Oefficient wellseparated pair decomposition and its applications
Publication
Publication
We present an external memory algorithm to compute a wellseparated pair decomposition (WSPD) of a given point set P in R<sup>d</sup> in O(sort(N)) I/Os using O(N/B) blocks of external memory, where N is the number of points in P, and sort(N) denotes the I/O complexity of sorting N items. (Throughout this paper we assume that the dimension d is fixed). We also show how to dynamically maintain the WSPD in O(logB N) I/O’s per insert or delete operation using O(N/B) blocks of external memory. As applications of the WSPD, we show how to compute a linear size tspanner for P within the same I/O and space bounds and how to solve the Knearest neighbor and Kclosest pair problems in O(sort(KN)) and O(sort(N +K)) I/Os using O(KN/B) and O((N +K)/B) blocks of external memory, respectively. Using the dynamic WSPD, we show how to dynamically maintain the closest pair of P in O(log<inf>B</inf> N) I/O’s per insert or delete operation using O(N/B) blocks of external memory.
Additional Metadata  

Citation 
Govindarajan, S. (Sathish), Lukovszki, T. (Tam´As), Maheshwari, A, & Zeh, N. (Norbert). (2000). I/Oefficient wellseparated pair decomposition and its applications.
