Practical Hypercube Computer Algorithms for Geometric Problems

Practical Hypercube Algorithms for Computational Geometry

Philip D. MacKenzie, Quentin F. Stout
Computer Science and Engineering, University of Michigan

Abstract: Many problems in computational geometry can be solved on the hypercube using a simple and practical technique, which we call cross-stitching. Given n inputs distributed one per processor on a hypercube with n processors, the cross-stitching paradigm runs in Θ(log² n) time with very low constants. We illustrate this form of 2-dimensional divide-and-conquer, consider some of its many applications, and show its practicality by computing exact communication constants for our algorithms. Cross-stitching utilizes bitonic sort as a key component.

For objects in 2-dimensional space, algorithms are given for dominance counting, 2-set dominance counting, closest pair, all points nearest neighbors, iso-oriented segment intersection, rectangle area, rectangle intersection, and visibility from a point. We also give an algorithm for 3-dimensional maxima.

Keywords: computational geometry, parallel algorithm, bitonic sort, hypercube computer, planar points, domination, nearest neighbors, iso-oriented intersections, visibility, cross-stitching

Complete paper. This paper appears in Proc. 3rd Symposium on Frontiers of Massively Parallel Computation (1990), pp. 75-78. It is a preliminary version, but we never wrote a final one.

Related Work:

This is an paper which examines the same problems and provides asymptotically optimal results, but the constants are so large they would never be useful in practice.

Here is a modest explanation of parallel computing, a tutorial on parallel computing, an overview of our work, and relevant papers.