Optimal Parallel Algorithms for Convex Polygon Separation

ID
TR-89-21
Authors
Norm Dadoun and David G. Kirkpatrick
Publishing date
September 1989
Abstract

Cooperative parallel algorithms are presented for determining convex polygon separation and constructing convex polygon mutual tangents. Given two $n$-vertex convex polygons, using $k$ CREW processors $(1 \leq k \leq n)$, each of these algorithms has an $ \Theta (\log n/(l + \log k)) $ time bound. This provides algorithms for these problems which run in $O(\log n)$ time sequentially or in constant time using a quasi-linear $(n^{\alpha}$ for some $\alpha > 0$) number of processors.

These algorithms make use of hierarchical data structures to solve their respective problems. The polygonal hierarchy used by our algorithms is available implicitly (with no additional preprocessing) within standard representations of polygons.