Abstract. A Semi-Separated Pair Decomposition (SSPD), with parameter s > 1, of a set S ⊂ R d is a set {(Ai, Bi)} of pairs of subsets of S such that for each i, there are balls DA i and DB i containing Ai and Bi respectively such that d(DA i , DB i ) ≥ s · min(radius(DA i ), radius(DB i )), and for any two points p, q ∈ S there is a unique index i such that p ∈ Ai and q ∈ Bi or vice-versa. In this paper, we use the SSPD to obtain the following results: First, we consider the construction of geometric t-spanners in the context of imprecise points and we prove that any set S ⊂ R d of n imprecise points, modeled as pairwise disjoint balls, admits a t-spanner with O(n log n/(t − 1) d ) edges which can be computed in O(n log n/(t − 1) d ) time. If all balls have the same radius, the number of edges reduces to O(n/(t − 1) d ). Secondly, for a set of n points in the plane, we design a query data structure for half-plane closest-pair queries that can be built in O(n 2 log 2 n) time using O(n log n) space and answers a query in O(n 1/2+ε ) time, for any ε > 0. By reducing the preprocessing time to O(n 1+ε ) and using O(n log 2 n) space, the query can be answered in O(n 3/4+ε ) time. Moreover, we improve the preprocessing time of an existing axis-parallel rectangle closest-pair query data structure from quadratic to near-linear. Finally, we revisit some previously studied problems, namely spanners for complete k-partite graphs and low-diameter spanners, and show how to use the SSPD to obtain simple algorithms for these problems.
Finally, we also give an O(n log 2 n)-time algorithm to build our halfplane RCP data structure, matching the preprocessing time in REF .
On the power of the semi-separated pair decomposition
WADS, LNCS Volume
Mathematics Computer Science