Practical Hypercube Algorithms for Computational Geometry
Philip D. MacKenzie,
Quentin F. Stout
Computer Science and Engineering, University of Michigan
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 Θ(log2 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.
computational geometry, parallel algorithm, bitonic sort, hypercube computer,
planar points, domination,
nearest neighbors, iso-oriented intersections, visibility, cross-stitching
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.
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,
overview of our work, and
Copyright © 2005-2017 Quentin F. Stout.