### 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.

report64.ps.gz