Optical Clustering on a Mesh- Connected Computer 1

In this paper, we present optimal parallel algorithms for optical clustering on a mesh-connected computer. Optical clustering is a clustering technique based on the principal of optical resolution, and is of particular interest in picture analysis. The algorithms we present are based on the application of parallel algorithms in computational geometry and graph theoryl In particular, we show that given a set S of N points in the Euclidean plane, the following problems can be solved in optimal O(x/-N) time on a mesh-connected computer of size N. 1. Determine the optical clusters of S with respect o a given separation parameter. 2. Given an interval [a,b] representing the number of optical clusters desired in the clustering of S, determine the range of the separation parameter that will result in such an optical clustering. KEY WORDS: Mesh-connected computer; optical clustering; image processing; computationai geometry; connected components