Name
Title | ||
|---|---|---|
An O((log log n)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 $\sqrt n\times \sqrt n$ was running in O(log2n) 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)2) time on a reconfigurable mesh of size $\sqrt n\times \sqrt n.$ With slight modifications, this algorithm can be implemented to run in O((log log n)2) time on a reconfigurable mesh of size ${\textstyle{{\sqrt n} \over {{\rm log\,log}\,n}}}\times {\textstyle{{\sqrt n} \over {{\rm log \,log}\,n}}}.$ 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 驴(log log n) time. Our result opens the door to an entire slew of efficient convex-hull-based algorithms on reconfigurable meshes. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/71.737694 | IEEE Transactions on Parallel and Distributed Systems |
Keywords | Field | DocType |
log log n,convex hull,Reconfigurable Meshes,Time Algorithm,n-processor reconfigurable mesh,Convex Hull,rm log,Sorted Points,efficient convex-hull-based algorithm,optimal convex hull algorithm,sublogarithmic time,sqrt n,latter algorithm,reconfigurable mesh | Reconfigurable mesh,Polygon mesh,Computer science,Image processing,Convex hull,Real-time computing,Artificial intelligence,Robotics,Distributed computing,Log-log plot,Parallel algorithm,Algorithm,Computational complexity theory | Journal |
Volume | Issue | ISSN |
9 | 12 | 1045-9219 |
Citations | PageRank | References |
5 | 0.50 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tatsuya Hayashi | 1 | 97 | 11.39 |
| Koji Nakano | 2 | 1165 | 118.13 |
| Stephen Olariu | 3 | 125 | 8.24 |