2009 | OriginalPaper | Chapter
On the Power of the Semi-Separated Pair Decomposition
Authors : Mohammad Ali Abam, Paz Carmi, Mohammad Farshi, Michiel Smid
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A Semi-Separated Pair Decomposition (SSPD), with parameter
s
> 1, of a set
$S\subset {\mathbb R}^d$
is a set {(
A
i
,
B
i
)} of pairs of subsets of
S
such that for each
i
, there are balls
$D_{A_i}$
and
$D_{B_i}$
containing
A
i
and
B
i
respectively such that
$d(D_{A_i},D_{B_i}) \geq s \cdot$
min ( radius
$(D_{A_i}$
) , radius
$(D_{B_i})$
), and for any two points
p
,
q
∈
S
there is a unique index
i
such that
p
∈
A
i
and
q
∈
B
i
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\subset {\mathbb R}^d$
of
n
imprecise points, modeled as pairwise disjoint balls, admits a
t-spanner
with
${\mathcal O}(n\log n/(t-1)^d)$
edges which can be computed in
${\mathcal O}(n\log n/(t-1)^d)$
time. If all balls have the same radius, the number of edges reduces to
${\mathcal 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
${\mathcal O}(n^2\log^2 n)$
time using
${\mathcal O}(n\log n)$
space and answers a query in
${\mathcal O}(n^{1/2+\epsilon})$
time, for any
ε
> 0. By reducing the preprocessing time to
${\mathcal O}(n^{1+\epsilon})$
and using
${\mathcal O}(n\log^2 n)$
space, the query can be answered in
${\mathcal O}(n^{3/4+\epsilon})$
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.