2009 | OriginalPaper | Buchkapitel
On the Power of the Semi-Separated Pair Decomposition
verfasst von : Mohammad Ali Abam, Paz Carmi, Mohammad Farshi, Michiel Smid
Erschienen in: Algorithms and Data Structures
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.