Loading...
Please wait, while we are loading the content...
Similar Documents
An o((log log n)²) time convex hull algorithm on reconfigurable meshes (1998).
| Content Provider | CiteSeerX |
|---|---|
| Author | Hayashi, Tatsuya Nakano, Koji Olariu, Stephan |
| Abstract | It was open for more than eight years to obtain an algorithm for computing the convex hull of a set of n sorted points in sub-logarithmic time on a reconfigurable mesh of size p n # p n. Our main contribution is to provide the first breakthrough: we propose an almost optimal algorithm running in O##log log n# 2 # time on a reconfigurable mesh of size p n # p n. With slight modifications this algorithm can be implemented to run in O##log log n# 2 # time on a reconfigurable mesh of size p n log log n # p n 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 efficient convex-hull-based algorithms on reconfigurable meshes. |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Reconfigurable Mesh Log Log Time Convex Hull Algorithm Convex Hull Log Log Time Latter Algorithm Convex-hull-based Algorithm First Breakthrough Sub-logarithmic Time Main Contribution Slight Modification N-processor Reconfigurable Mesh Size Log Log Log Log Optimal Algorithm |
| Content Type | Text |
