Scalable 2d convex hull and triangulation algorithms for coarse grained multicomputers.

A. Ferreira, A. Rau-Chaplin, and S. Ubeda

Abstract: In this paper we describe scalable parallel algorithms for building the Convex Hull and a Triangulation of a given point set in ${\cal R}^2$. These algorithms are designed for the {\em coarse grained multicomputer} model: $p$ processors with $O(\frac{n}{p}) \gg O(1) $ local memory each, connected to some arbitrary interconnection network (e.g. mesh, hypercube, omega). They scale over a large range of values of $n$ and $p$, assuming only that $n \geq p^{{1+\epsilon}}$ ($\epsilon > 0$) and require time $O(\frac{T_{sequential}}{p} + T_s(n,p))$, where $T_s(n,p)$ refers to the time of a global sort of $n$ data on a $p$ processor machine. Furthermore, they involve only a constant number of global communication rounds. Since computing either 2d Convex Hull or Triangulation requires time $T_{sequential}=\Theta(n\log n)$ these algorithms either run in optimal time, $\Theta(\frac{n\log n}{p})$, or in sort time, $T_s(n,p)$, for the interconnection network in question. These results become optimal when $\frac{T_{sequential}}{p}$ dominates $T_s(n,p)$ or for interconnection networks like the mesh for which optimal sorting algorithms exist.