PARALLEL COMPUTATION OF INTERNAL AND EXTERNAL FARTHEST NEIGHBORS IN SIMPLE POLYGONS

We present efficient parallel algorithms for two problems in simple polygons: the all-farthest neighbors problem and the external all-farthest neighbors problem. The all-farthest neighbors problem is that of computing, for each vertex p of a simple polygon P, a point psi(p) in P farthest from p when the distance between p and psi(p) is measured by the shortest path between them constrained to lie inside P. The external all-farthest neighbors problem is that of computing, for each vertex p of a simple polygon P, a point phi(p) on (the boundary of) P farthest from p when the distance between p and phi(p) is measured by the shortest path between them constrained to lie outside (the interior of) P. Both our algorithms run in O(log(2) n) time on a CREW PRAM with O(n) processors. Our divide-and-conquer method for the external all-farthest neighbors problem, in fact, leads to a new O(n log n) time serial algorithm that matches the currently best serial algorithm for this problem, but is simpler.