Kirkpatrick, David G.Seidel, Raimund2007-04-232007-04-231983-10http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-577https://hdl.handle.net/1813/6417We 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 of vertices found to be on the hull. We also show that this algorithm is asymptotically worst case optimal on a rather realistic 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.1229097 bytes378517 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report