Loading...
Please wait, while we are loading the content...
Similar Documents
Time- and VLSI-Optimal Convex Hull Computation on Meshes with Multiple Broadcasting (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bokka, V. Gurla, H. Olariu, S. Schwing, J. L. |
| Abstract | Computing the convex hull of a planar set of points is one of the most extensively investigated topics in computational geometry. Our main contribution is to present the first known general-case, time- and VLSI-optimal, algorithm for convex hull computation on meshes with multiple broadcasting. Specifically, we show that for every choice of a positive integer constant c, the convex hull of a set of m (n 1 2 + 1 2c m n) points in the plane stored in the first d m p n e columns of a mesh with multiple broadcasting of size p n \Theta p n can be computed in \Theta( m p n ) time. Our algorithm features a very attractive additional property, namely that the time to input the data, the time to compute the convex hull, as well as the time to output the result are essentially the same. |
| File Format | |
| Volume Number | 56 |
| Journal | INFORMATION PROCESSING LETTERS |
| Language | English |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Multiple Broadcasting Vlsi-optimal Convex Hull Computation Convex Hull Computational Geometry Attractive Additional Property Convex Hull Computation Investigated Topic Size Theta Main Contribution First Column Positive Integer Constant Planar Set |
| Content Type | Text |
| Resource Type | Article |
