ICS Theory Group

April 23, Spring Quarter 2010: Theory Seminar

1:00pm in ICS 243

Geometric Algorithms for Private-Cache Chip Multiprocessors

Nodari Sitchinava, Aarhus Univ.

Abstract: We study techniques for obtaining efficient algorithms for geometric problems on private-cache chip multiprocessors in the Parallel External Memory (PEM) model. We solve the problems of orthogonal line segment intersection reporting, batched orthogonal range reporting and rectangle intersection reporting. To obtain nearly optimal algorithms for these problems, we introduce a parallel distribution sweeping technique inspired by its sequential counterpart. We also show how to obtain optimal algorithms for interval stabbing counting, 1-D range counting, weighted 2-D dominance counting, and for computing 3-D maxima, 2-D lower envelopes, and 2-D convex hulls via adaptations of either the PEM merge sort algorithm or corresponding PRAM algorithms.