Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.