Optimal parallel algorithms for finding proximate points, with applications

Consider a set P of points in the plane sorted by x-coordinate. A point p in P is said to be a proximate point if there exists a point q on the x-axis such that p is the closest point to q over all points in P. The proximate point problem is to determine all the proximate points in P. Our main contribution is to propose optimal parallel algorithms for solving instances of size n of the proximate points problem. We begin by developing a work-time optimal algorithm running in O(log log n) time and using n/loglogn Common-CRCW processors. We then go on to show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. In addition to being work-time optimal, our EREW algorithm turns out to also be lime-optimal. Our second main contribution is to show that the proximate points problem finds interesting, and quite unexpected, applications to digital geometry and image processing. As a first application, we present a work-time optimal parallel algorithm for finding the convex hull of a set of n points in the plane sorted by x-coordinate; this algorithm runs in O(log log n) time using n/loglogn Common-CRCW processors. We then show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. Next, we show that the proximate points algorithms afford us work-time optimal (resp. time-optimal) parallel algorithms for various fundamental digital geometry and image processing problems. Specifically, we show that the Voronoi map, the Euclidean distance map, the maximal empty circles, the largest empty circles, and other related problems involving a binary image of size n x n can be solved in O(log log n) time using n(2)/loglogn Common-CRCW processors or in O(log n) time using n(2)/EREW processors.