PARALLEL ALGORITHMS FOR COMPUTING THE CLOSEST VISIBLE VERTEX PAIR BETWEEN TWO POLYGONS

Abstract

In this paper, we are concerned with the closest visible vertex pair problem, which is defined as follows: we are given two simple non-intersecting polygons P and Q with in and n vertices respectively, we are asked to find a closest visible pair of vertices between P and Q. We shall show that we can solve this problem in O(log(m + n)) time with O(m + n) processors in the CREW PRAM model.