@inbook {IOPORT.05779703,
    author       = {Ajwani, Deepak and Sitchinava, Nodari and Zeh, Norbert},
    title        = {Geometric algorithms for private-cache chip multiprocessors (extended abstract).},
    year         = {2010},
    booktitle    = {Algorithms -- ESA 2010. 18th annual European symposium, Liverpool, UK, September 6--8, 2010. Proceedings, Part II},
    isbn         = {978-3-642-15780-6},
    pages        = {75-86},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-15781-3_7},
    abstract     = {Summary: We study techniques for obtaining efficient algorithms for geometric problems on private-cache chip multiprocessors. We 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. What distinguishes these problems from the ones in the previous group is the variable output size, which requires I/O-efficient load balancing strategies based on the contribution of the individual input elements to the output size. To obtain nearly optimal algorithms for these problems, we introduce a parallel distribution sweeping technique inspired by its sequential counterpart.},
    identifier   = {05779703},
}