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 crossstitching.
Given n inputs distributed one per processor
on a hypercube with n processors, the crossstitching paradigm
runs in Θ(log^{2} n) time with very low constants.
We illustrate this form of 2dimensional divideandconquer,
consider some of its many applications, and show its practicality
by computing exact communication constants for our algorithms.
Crossstitching utilizes bitonic sort as a key component.
For objects in 2dimensional space, algorithms are given for dominance counting, 2set dominance counting, closest pair, all points nearest neighbors, isooriented segment intersection, rectangle area, rectangle intersection, and visibility from a point.
We also give an algorithm for 3dimensional maxima.
Keywords:
computational geometry, parallel algorithm, bitonic sort, hypercube computer,
planar points, domination,
nearest neighbors, isooriented intersections, visibility, crossstitching
Complete paper.
This paper appears in Proc. 3rd Symposium on Frontiers of Massively Parallel Computation (1990), pp. 7578. 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.

Copyright © 20052016 Quentin F. Stout. 