2006-08-01
I/O-efficient well-separated pair decomposition and applications
Publication
Publication
Algorithmica , Volume 45 - Issue 4 p. 585- 614
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 | |
|---|---|
| Closest-pair problem, Computational geometry, External-memory algorithms, Proximity problems, Spanners, Well-separated pair decomposition | |
| dx.doi.org/10.1007/s00453-005-1197-3 | |
| Algorithmica | |
| Organisation | Computational Geometry Lab |
|
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
|
|