An Efficient Convex Hull Algorithm on the Reconfigurable Mesh
Sung‐Ryul Kim, Kunsoo Park · Journal of Electrical Engineering and Information Science · 1998
Consider the two-dimensional sorted-set convex hull problem: Given N points in a plane sorted by the x coordinates, compute the convex hull of the points. We propose an O(logNloglogN)-time algorithm that solves the sorted-set convex hull problem on an N^(l/2)×N^(1/2) reconfigurable mesh. The best known algorithm for the problem on an N^(l/2)×N^(1/2) reconfigurable mesh takes 0(1og²N) time. Although there is a constant-time algorithm on an N×N reconfigurable mesh for the general two-dimensional convex hull problem, the general convex hull problem requires θ(N^(l/2)) time on an N^(l/2)×N^(1/2) reconfigurable mesh due to bandwidth constraints.