University of 7th November at Carthage
The authors study techniques for obtaining efficient algorithms for geometric problems on private-cache chip multiprocessors. They 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. These results are obtained by analyzing adaptations of either the PEM merge sort algorithm or PRAM algorithms. For the second group of problems-orthogonal line segment intersection reporting, batched range reporting, and related problems-more effort is required.