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.
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. |
Copyright © 2005-2016 |