## 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.