Skip to main content


eCommons@Cornell

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

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6417
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
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-577
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.
URI: http://hdl.handle.net/1813/6417
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