Asymptotically Efficient Hypercube Algorithms for Computational Geometry

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


Abstract: We present hypercube algorithms which solve many fundamental computational geometry problems. These algorithms use decomposition techniques which enable them to asymptotically outperform the fastest previous algorithms for these problems. Previous algorithms all run in Θ(log2 n) time, even when using a sorting routine which runs in o(log2 n) time. If sorting can be done in Θ(Sort(n)) time then our algorithms for 2-Set Dominance Counting, 3-Dimensional Maxima, Closest pair, and All Points Nearest Neighbors run in Θ(Sort(n) loglog n) time, and our algorithms for Triangulation and Visibility from a Point run in Θ(Sort(n)) time.

Keywords: parallel computer, hypercube computer, sorting, domination, nearest neighbors, Voronoi diagram, parallel algorithm, computational geometry

Complete paper. This paper appears in Proc. 3rd Symposium on Frontiers of Massively Parallel Computation (1990), pp. 8-11. 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 far more practical algorithms, though they are not asymptotically optimal.

Here is a modest explanation of parallel computing, a tutorial on parallel computing, an overview of our work, and relevant papers.
Quentin's Home Copyright © 2005-2016