DETERMINING THE SEPARATION OF SIMPLE POLYGONS

Given simple polygons P and Q, their separation, denoted by sigma(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 is an element of P and q is an element of Q. The algorithm runs in O(log n) time using O(n) processors on a CREW PRAM, where n = vertical bar P vertical bar + vertical bar Q vertical bar. This algorithm is time-optimal and improves by a factor of O(log n) on the time complexity of previous parallel methods. The algorithm can be implemented serially in Theta(n) time, which gives the first optimal sequential algorithm for determining the 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.