A Fast Adaptive Convex Hull Algorithm on Two-Dimensional Processor Arrays with a Reconfigurable Bus System

A bus system that can change dynamically to suit computational needs is referred to as reconfigurable. We present a fast adaptive convex hull algorithm on a twodimensional processor array with a reconfigurable bus system. Specifically, we show that computing the convex hull of a planar set of n points takes O( log n log m ) time on a reconfigurable mesh of size nm \Theta n with 3 m n. Our result implies that the convex hull of n points in the plane can be computed in O(1) time on a reconfigurable mesh of size n 1:5 \Theta n. Index Terms: reconfigurable meshes, bus systems, adaptive algorithms, convex hull, computational geometry. 1 Introduction Recent advances in VLSI have made it possible to build massively parallel machines featuring many thousands of cooperating processors. This increase in computational power does not, however, translate into increased performance of the same order of magnitude. One of the reasons seems to be that interprocessor communications and simultane..