Technical Reports

The ICICS/CS Reading Room

UBC CS TR-89-21 Summary

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