摘要：Given a set P of n points in two dimensions, the aim of a clustering algorithm is to find a subset of k points such that some measure for this subset is minimized. We present efficient parallel algorithms for two clustering problems, namely,(i) a k -point subset with minimum L1 -diameter and(ii) a k -point subset with minimum L1 -perimeter. We give a unified framework for solving these problems in parallel. We decompose the original problem into O(n=k) subproblems, each of size O(k) by imposing a grid on the point set. We solve all these subproblems simultaneously in parallel and obtain the global optimal solution from the solutions of the subproblems. For the L1 -perimeter case, our algorithm runs in O(log 2 n) time and requires O(n log 2 n +nk 2 log 2 k) work. For the L1 -diameter case, our algorithm runs in O(log 2 n +log 2 k log log k log k) time and requires O(n log 2 n) work. For each problem, the work done by our algorithm is close to the complexity of the best known sequential algorithm. Our algorithms are designed for the CREW PRAM model of parallel computation.
