FINDING A CLOSEST VISIBLE VERTEX PAIR BETWEEN 2 POLYGONS

Given nonintersecting simple polygoris P and Q, two vertices p is an element of P and q is an element of Q are said to be visible if <($$)over bar>pq does not properly intersect P or Q. We present a parallel algorithm for finding a closest pair among all visible pairs (p,q) p is an element of P and q is an element of Q. The algorithm runs in time O(log n) using O(n) processors on a CREW PRAM, where n = \P\+\Q\. This algorithm can be implemented serially in O(n) time, which gives a new optimal sequential solution for this problem.