Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431085 | Journal of Discrete Algorithms | 2010 | 14 Pages |
Abstract
Given a geometric graph G=(S,E)G=(S,E) in RdRd with constant dilation t, and a positive constant ε , we show how to construct a (1+ε)(1+ε)-spanner of G with O(|S|)O(|S|) edges using O(sort(|E|))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⊂RdS⊂Rd using O(sort(|S|))O(sort(|S|)) memory transfers.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Fabian Gieseke, Joachim Gudmundsson, Jan Vahrenhold,