Time- and VLSI-optimal convex hull computation on meshes with multiple broadcasting

摘要

Computing the convex hull of a planar set of points is one of the most extensively investigated topics in computational geometry. Our main contribution is to present the first known general-case, time- and VLSI-optimal, algorithm for convex hull computation on meshes with multiple broadcasting. Specifically, we show that for every choice of a positive integer constant c, the convex hull of a set of m(n/sup 1/2 + 1/2 c//spl les/m/spl les) points in the plane stored in the first [m//spl radic] columns of a mesh with multiple broadcasting of size /spl radic/spl times//spl radic can be computed in /spl Theta/(m//spl radic) time. Our algorithm features a very attractive additional property, namely that the time to input the data, the time to compute the convex hull, as well as the time to output the result are essentially the same.