In Proc. 29th International Colloquium on Automata, Languages, and Programming, volume 2380 of Lecture Notes in Computer Science, pages 426-438. Springer Verlag, Berlin, 2002.
We adapt the distribution sweeping method to the cache oblivious model. Distribution sweeping is the name used for a general approach for divide-and-conquer algorithms where the combination of solved subproblems can be viewed as a merging process of streams. We demonstrate by a series of algorithms for specific problems the feasibility of the method in a cache oblivious setting. The problems all come from computational geometry, and are: orthogonal line segment intersection reporting, the all nearest neighbors problem, the 3D maxima problem, computing the measure of a set of axis-parallel rectangles, computing the visibility of a set of line segments from a point, batched orthogonal range queries, and reporting pairwise intersections of axis-parallel rectangles. Our basic building block is a simplified version of the cache oblivious sorting algorithm Funnelsort of Frigo et al., which is of independent interest.
Copyright notice© Springer-Verlag Berlin Heidelberg 2002. All rights reserved.
Online version
icalp02cache.pdf (152 Kb)
DOI
Links
BIBTEX entry
@incollection{icalp02cache,
author = "Gerth Stølting Brodal and Rolf Fagerberg",
booktitle = "Proc. 29th International Colloquium on Automata, Languages, and Programming",
doi = "10.1007/3-540-45465-9_37",
isbn = "978-3-540-43864-9",
pages = "426-438",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Cache Oblivious Distribution Sweeping",
volume = "2380",
year = "2002"
}
Other versions