Technical Reports

The ICICS/CS Reading Room

UBC CS TR-83-07 Summary

Marriage Before Conquest: A Variation on the Divide \& Conquer Paradigm, October 1983 David G. Kirkpatrick and Raimund Seidel

We present a new planar convex hull algorithm with worst case time complexity $O(n \log H)$ where $n$ is the size of the input set and $H$ is the size of the output set, i.e. the number ot vertices found to be on the hull. We also show that this algorithm is asymptotically worst case optimal on a rather realisic model of computation even if the complexity of the problem is measured in terms of input as well as output size. The algorithm relies on a variation of the divide-and-conquer paradigm which we call the ``marriage-before-conquest'' principle and which appears to be interesting in its own right.

If you have any questions or comments regarding this page please send mail to