# The ICICS/CS Reading Room

## UBC CS TR-89-21 Summary

- No on-line copy of this technical report is available.

- Optimal Parallel Algorithms for Convex Polygon Separation, September 1989 Norm Dadoun and David G. Kirkpatrick
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.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.