TIME-OPTIMAL AND VLSI-OPTIMAL CONVEX-HULL COMPUTATION ON MESHES WITH MULTIPLE BROADCASTING

Our main contribution is to present the first known general-case, time - and VLSI-optimal, algorithm for convex hull computation on meshes wi th multiple broadcasting. Specifically, we show that for every choice of a positive constant epsilon, the convex hull of a set of an arbitra ry set of m (n(1/2+epsilon) less than or equal to m less than or equal to n) points in the plane input in the first [m/root n] columns of a mesh with multiple broadcasting of size root n x root n can be compute d in Theta(m/root n) time.