We present an external-memory algorithm to compute a well-separated pair decomposition (WSPD) of a given point set S in d in O(sort(N)) I/Os, where N is the number of points in S and sort(N) denotes the I/O-complexity of sorting N items. (Throughout this paper we assume that the dimension d is fixed.) As applications of the WSPD, we show how to compute a linear-size t-spanner for S within the same I/O-bound and how to solve the K-nearest-neighbour and K-closest-pair problems in O(sort(KN)) and O(sort(N+K)) I/Os, respectively.

Additional Metadata
Keywords Closest-pair problem, Computational geometry, External-memory algorithms, Proximity problems, Spanners, Well-separated pair decomposition
Persistent URL dx.doi.org/10.1007/s00453-005-1197-3
Journal Algorithmica
Govindarajan, S. (Sathish), Lukovszki, T. (Tamas), Maheshwari, A, & Zeh, N. (Norbert). (2006). I/O-efficient well-separated pair decomposition and applications. Algorithmica, 45(4), 585–614. doi:10.1007/s00453-005-1197-3