Parallel algorithms for proximity problems /
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1990.
|
| Subjects: | |
| Online Access: | Link to ProQuest copy Link to OAKTrust copy |
| Abstract: | Proximity problems deal with "closeness" of points in a finite set in k-dimensional space under some distance metric L (subscript p). These problems arise in many applications such as pattern recognition, wire routing, and air traffic control. Parallel algorithms for a number of proximity problems using the concurrent-read exclusive-write parallel random access machine (CREW PRAM) model are presented. For the All Nearest Neighbors and Closest Pair problems, our O (log(superscript k-1)N) algorithm may be used for points in any given metric L (subscript p) in k-dimensional space. The All Nearest Neighbors Between Sets and Closest Pair Between Sets problems may be solved O (log(superscript k-1)N) time for points in the L ₁ metric in k-dimensional space and for points in the L (subscript infinity symbol) metric in the plane. We give two O (log(superscript k)N) Minimum Spanning Tree algorithms. The first algorithm may be used for points in the L ₁metric in k-dimensional space and for points in the L (subscript infinity symbol) metric in the plane. The second algorithm finds the Minimum Spanning Tree for a set of points in the Euclidean plane. |
|---|---|
| Item Description: | "Major subject: Computer science." Typescript (photocopy). Vita. |
| Physical Description: | x, 69 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references. |