Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

TY - JOUR

T1 - Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

AU - Gieseke, Fabian

AU - Gudmundsson, Joachim

AU - Vahrenhold, Jan

PY - 2010

Y1 - 2010

N2 - Given a geometric graph G=(S,E) in Rd with constant dilation t, and a positive constant , we show how to construct a (1+)-spanner of G with O(|S|) edges using O(sort(|E|)) memory transfers in the cache-oblivious model of computation. The main building block of our algorithm, and of independent interest in itself, is a new cache-oblivious algorithm for constructing a well-separated pair decomposition which builds such a data structure for a given point set S⊂Rd using O(sort(|S|)) memory transfers.

AB - Given a geometric graph G=(S,E) in Rd with constant dilation t, and a positive constant , we show how to construct a (1+)-spanner of G with O(|S|) edges using O(sort(|E|)) memory transfers in the cache-oblivious model of computation. The main building block of our algorithm, and of independent interest in itself, is a new cache-oblivious algorithm for constructing a well-separated pair decomposition which builds such a data structure for a given point set S⊂Rd using O(sort(|S|)) memory transfers.

KW - Cache-oblivious algorithms

KW - External-memory algorithms

KW - Geometric graphs

KW - Spanners

KW - Well-separated pair decomposition

UR - http://www.scopus.com/inward/record.url?scp=77955710007&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2010.03.001

DO - 10.1016/j.jda.2010.03.001

M3 - Journal article

AN - SCOPUS:77955710007

SN - 1570-8667

VL - 8

SP - 259

EP - 272

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 3

ER -