Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: The Ultimate Planar Convex Hull Algorithm ?
Authors: Kirkpatrick, David G.
Seidel, Raimund
Keywords: computer science
technical report
Issue Date: Oct-1983
Publisher: Cornell University
Abstract: 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 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.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
83-577.pdf1.2 MBAdobe PDFView/Open
83-577.ps369.65 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us