Skip to main content
Erschienen in:
Buchtitelbild

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.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
On the Power of the Semi-Separated Pair Decomposition
verfasst von
Mohammad Ali Abam
Paz Carmi
Mohammad Farshi
Michiel Smid
Copyright-Jahr
2009
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-03367-4_1