# Cache Oblivious Distribution Sweeping

Technical Report, BRICS-RS-02-18, BRICS, Department of Computer Science, Aarhus University, 21 pages, 2009.

## Abstract

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.

**Online version**
brics-rs-02-18.pdf (185 Kb)

**BIBT**_{E}X entry

@techreport{brics-rs-02-18,
author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
institution = "BRICS, Department of Computer Science, Aarhus University",
issn = "0909-0878",
number = "BRICS-RS-02-18",
pages = "21",
title = "Cache Oblivious Distribution Sweeping",
year = "2009"
}