An O((log log n)/sup 2/) time algorithm to compute the convex hull of sorted points on reconfigurable meshes

Abstract

The problem of computing the convex hull of a set of n sorted points in the plane is one of the fundamental tasks in image processing, pattern recognition, cellular network design, and robotics, among many others. Somewhat surprisingly, in spite of a great deal of effort, the best previously known algorithm to solve this problem on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n was running in O(log2 n) time. It was open for more than ten years to obtain an algorithm for this important problem running in sublogarithmic time. Our main contribution is to provide the first breakthrough: we propose an almost optimal convex hull algorithm running in O((log log n)/sup 2/) time on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n. With slight modifications, this algorithm can be implemented to run in O((log log n)/sup 2/) time on a reconfigurable mesh of size /spl radic/n/loglogn/spl times//spl radic/n/loglogn. Clearly, the latter algorithm is work-optimal. We also show that any algorithm that computes the convex hull of a set of n sorted points on an n-processor reconfigurable mesh must take /spl Omega/(log log n) time. Our result opens the door to an entire slew of efficient convex-hull-based algorithms on reconfigurable meshes.