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 | |
|---|---|
| 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 |
| Citation |
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
|