An O((log log n)2) time convex hull algorithm on reconfigurable meshes

The problem of obtaining an algorithm for computing the convex hull of a set of n sorted points in sub-logarithmic time on a reconfigurable mesh of size √n×√n has been open for eight years. The authors provide the first breakthrough: they propose an almost optimal algorithm running in O((log log n)²) time on a reconfigurable mesh of size √n×√n. With slight modifications this algorithm can be implemented to run in O((log log n) ²) time on a reconfigurable mesh of size √n/log log n×√n/log log n. Clearly, the latter algorithm is work-optimal. They 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 Ω(log log n) time. The result opens the door to efficient convex-hull-based algorithms on reconfigurable meshes