Technical Reports

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. \n\n 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.