Parallel algorithms for geometric problems on networks of processors
J.-J. Tsay · 2002
In this paper, we present algorithms for solving several basic geometric problems of size n in a network of p processors each with O(n/p) local memory. Our algorithms achieve the best possible (up to a constant factor) time bound in hypercubic parallel architectures such as hypercube, shuffle exchange and cube connected cycles, provided that n /spl les/ p/sup 1/+/spl epsi/ for some positive constant /spl epsi/. Our algorithms use only sorting and parallel prefixes that involve interprocessor communications, and can be easily implemented in commercially available parallel computers. Experimentation on nCUBE parallel computers show that our algorithms run efficiently.>