Meshes and Pyramids | |
List of Figures | |
Preface | |
Overview of Chapters | |
Recommended Use | |
Correspondence | |
Acknowledgments | |
Overview | |
Introduction | |
Models of Computation | |
Preliminaries | |
Classification Schemes | |
Mesh Computer | |
Pyramid Computer | |
Mesh-of-Trees Architecture | |
Hypercube | |
Pram | |
Forms of Input | |
Problems | |
Graph and Image Problems | |
Computational Geometry Problems | |
Data Movement Operations | |
Sample Algorithms | |
Component Labeling for Digitized Picture Input | |
Convex Hull for Planar Point Data Input | |
Further Remarks | |
Fundamental Mesh Algorithms | |
Introduction | |
Definitions | |
Lower Bounds | |
Primitive Mesh Algorithms | |
Row and Column Rotations | |
Passing a Row (Column) Through the Mesh | |
Semigroup Operations, Reporting, and Broadcasting | |
Parallel Prefix | |
Matrix Algorithms | |
Matrix Transposition | |
Matrix Multiplication | |
Transitive Closure | |
Matrix Inverse | |
Algorithms Involving Ordered Data | |
Sorting | |
Rotating Data within Intervals | |
Semigroup Computation within Intervals | |
Concurrent Read and Concurrent Write | |
Compression | |
Further Remarks | |
Mesh Algorithms for Images and Graphs | |
Introduction | |
Fundamental Graph Algorithms | |
Bridge Edges | |
Articulation Points | |
Minimum Spanning Tree | |
Connected Components | |
Counting Connected Components | |
Labeling Connected Components | |
Internal Distances | |
Convexity | |
External Distances | |
Further Remarks | |
Mesh Algorithms for Computational Geometry | |
Introduction | |
Preliminaries | |
Initial Conditions | |
Lower Bounds | |
Fundamental Operations on the Mesh | |
The Convex Hull | |
Smallest Enclosing Figures | |
Nearest Point Problems | |
Line Segments and Simple Polygons | |
Intersection of Convex Sets | |
Diameter | |
Iso-oriented Rectangles and Polygons | |
Voronoi Diagram | |
Algorithm | |
Applications | |
Further Remarks | |
Tree-like Pyramid Algorithms | |
Introduction | |
Definitions | |
Lower Bounds | |
Fundamental Algorithms | |
Initializing Identity Registers | |
Bit Counting Problems | |
Computing Commutative Associative Binary Functions | |
Point Queries | |
Image Algorithms | |
Convexity Properties | |
Digitized Straight Line Segments | |
Further Remarks | |
Hybrid Pyramid Algorithms | |
Introduction | |
Graphs as Unordered Edges | |
Data Movement Operations | |
Component Labeling | |
Minimal Spanning Forests | |
Graphs as Adjacency Matrices | |
Data Movement Operations | |
Component Labeling and Minimal Spanning Forests | |
Digitized Pictures | |
Data Movement Operations | |
Component Labeling | |
Nearest Neighbors | |
Convexity | |
Data Movement Operations | |
Enumerating Extreme Points | |
Applications of Extreme Points | |
Data Movement Operations | |
Pyramid Read, Pyramid Write, and Count_keys | |
Pyramid Matrix Read and Pyramid Matrix Write | |
Funnel Read and Reducing a Function | |
Optimality | |
Further Remarks | |
Order Notation | |
Recurrence Equations | |
Bibliography | |
Table of Contents provided by Publisher. All Rights Reserved. |
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.