Technical Report No. 64, December 1994 - Abstract

Amitava Datta:
Efficient Parallel Algorithms for Geometric Clustering and Partitioning Problems

We present efficient parallel algorithms for some geometric clustering and partitioning problems. Our algorithms run in the CREW PRAM model of parallel computation. Given a point set P of n points in two dimensions, the clustering problems are to find a k-point subset such that some measure for this subset is minimized. We consider the problems of finding a k-point subset with minimum L_{infinity} perimeter and minimum L_{infinity} diameter. For the L_{infinity} perimeter case, our algorithm runs in O(log^2(n)) time and O(n*log^2(n) + n*k^2*log^2(k)) work. For the L_{infinity} diameter case, our algorithm runs in O(log^2(n) + log^2(k)*log(log k)*log^(*)(k)) time and O(n*log^2(n)) work. We consider partitioning problems of the following nature. Given a planar point set S (|S|=n), a measure mu acting on S and a pair of values mu_1 and mu_2, does there exist a bipartition S=S_1 U S_2 such that mu(S_1) <= mu_i for i=1,2 ? We consider several measures like diameter under L_{infinity} and L_1 metric; area, perimeter of the smallest enclosing axes-parallel rectangle and the side length of the smallest enclosing axes-parallel square. All our parallel algorithms for partitioning problems run in O(log n) time using O(n) processors in the CREW PRAM. In our algorithms, we use an optimal parallel construction of a range tree. We also show how to perform report mode orthogonal range queries in optimal O(log n) time using O(1+k/log n) processors, where k is the number of points inside the query range. The processor-time product for this range reporting algorithm is optimal.