Title :
Optimal parallel algorithms for finding proximate points, with applications
Author :
Hayashi, Tatsuya ; Nakano, Koji ; Olariu, Stephan
Author_Institution :
Dept. of Electr. & Comput. Eng., Nagoya Inst. of Technol., Japan
fDate :
12/1/1998 12:00:00 AM
Abstract :
Consider a set P of points in the plane sorted by the 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 time-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/logn 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
Keywords :
computational complexity; computational geometry; concurrency theory; image processing; parallel algorithms; Common-CRCW processors; EREW processors; convex hull; digital geometry; digital image processing; optimal parallel algorithms; proximate point finding; work-time optimal parallel algorithm; x-axis; x-coordinate sorted plane; Application software; Computer Society; Euclidean distance; Geometry; Image analysis; Image processing; Parallel algorithms; Pattern recognition; Performance evaluation; Phase change random access memory;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on