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 firstname.lastname@example.org.