Research Seminar - May 28, 1999

Abstract

We present an O(1) time algorithm for constructing the Voronoi diagram of n planar points. Our algorithm runs on a reconfigurable mesh of size O(n^2+e), for every fixed e > 0. The best known algorithm for this problem has a running time of O(lognloglogn) on a reconfigurable mesh of size O(n²). We also prove that W(n²) is a lower bound on the size of the mesh required for constructing the Voronoi diagram in O(1) time. Hence, our processor requirement of O(n^2+e) is close to optimal. Our algorithm can be modified easily to run in O(logn) time on a reconfigurable mesh of size O(n²) and this is again an improvement over the best known algorithm.

**This is a joint work with S. Soundaralakshmi.