Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal Computation of the Contour of Maximal Elements on Mesh-Connected Computers (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Murshed, M. Manzur Hegland, Markus |
| Abstract | : Dehne presented an optimal algorithm to compute the contour of the maximal elements of n planar points on a p n \Theta p n mesh. We have calculated that Dehne's algorithm requires 23 p n steps and we have been able to reduce the required steps to 19 p n through pre-sorting and using an efficient strategy in dividing the mesh into halves. It has also been established that any implementation of Dehne's algorithm requires at least 15 p n steps. We have further developed a new optimal algorithm which requires at most 10 p n steps. Key Words: Mesh-Connected Computer, Parallel Algorithm, Computational Geometry. 1 Introduction Despite the large communication diameter, the meshconnected computer, defined in Sec. 2.1, has been given considerable attention because of its simplicity, regularity of interconnection pattern, and modularity of the layout which make it an ideal model for VLSI applications. A large number of efficient algorithms have been developed on meshes for a variety... |
| File Format | |
| Language | English |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Maximal Element Mesh-connected Computer Optimal Computation Computational Geometry Planar Point Parallel Algorithm New Optimal Algorithm Optimal Algorithm Efficient Algorithm Efficient Strategy Ideal Model Vlsi Application Theta Mesh Large Number Large Communication Diameter Interconnection Pattern Considerable Attention Key Word Required Step |
| Content Type | Text |
| Resource Type | Technical Report |
