Parallel algorithms for proximity problems

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.