An O((log log n)/sup 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 /spl radic/spl times//spl radic has been open for eight years. The authors provide the first breakthrough: they propose an almost optimal algorithm running in O((log log n)/sup 2/) time on a reconfigurable mesh of size /spl radic/spl times//spl radic. 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/log log n/spl times//spl radic/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 /spl Omega/(log log n) time. The result opens the door to efficient convex-hull-based algorithms on reconfigurable meshes.