I/O Effizient Well-Separated Pair Decomposition and its Applications

Sathish Govindarajan, Tamás Lukovszki, Anil Maheshwari, and Norbert Zeh

Abstract

We present an external memory algorithm to compute a a well seperated pair decomposition (WSPD) of a given point set P in d-dimensional space 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/delete operation using O(N/B) blocks of external memory. As applications of the WSPD, we show how to compute a linear size t-spanner for P within the same I/O and space bounds and to solve the K-nearest neighbor and K-closest 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 maintain the dynamic closest pair of P in O(logB N) I/O's per insert/delete operation using O(N/B) blocks of external memory. These results make significant progress in providing external memory algorithms for higher-dimensional geometric problems.