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 Θ(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.
Keywords:
parallel computer, divide-and-conquer, bitonic sort, domination,
nearest neighbors, iso-oriented intersections, visibility, cross-stitching,
parallel algorithm, theoretical computer science, supercomputing
This is an abstract
of a paper which examines the same problems and provides asymptotically
optimal results, which are probably not useful in practice.
