# The ICICS/CS Reading Room

## UBC CS TR-83-07 Summary

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

- 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
help@cs.ubc.ca.