Determining The Separation Of Simple Polygons

Given simple polygons P and Q, their separation, denoted by oe(P; Q), is defined to be the minimum distance between their boundaries. We present a parallel algorithm for finding a closest pair among all pairs (p; q), p 2 P and q 2 Q. The algorithm runs in O(logn) time using O(n) processors on a CREW PRAM, where n = jP j + jQj. This algorithm is time-optimal and improves by a factor of O(logn) on the time complexity of previous parallel methods. The algorithm can be implemented serially in \Theta(n) time, which gives the first optimalsequential algorithm for determiningthe separation of simple polygons. Our results are obtained by providing a unified treatment of the separation and the closest visible vertex problems for simple polygons. Keywords: separation, simple polygon, parallel algorithm, sequential algorithm. 1. Introduction Computing the minimum distance between two simple polygons P and Q is a well studied problem in computational geometry. There are two common variants of ..