@inproceedings{sitchinava-esa10,
  author = "Deepak Ajwani and Nodari Sitchinava and Norbert Zeh", 
  title = "Geometric algorithms for private-cache chip multiprocessors", 
  booktitle = "Proceedings of the 18th European Symposium on Algorithms",
  series = "ESA '10", 
  pages  = "75-86",
  year  = 2010,
  month = 9,
  doi = "10.1007/978-3-642-15781-3_7",
  abstract = "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."
}