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/6624
Title: Output-Size Sensitive Algorithms for Constructive Problems in Computational Geometry
Authors: Seidel, Raimund
Keywords: computer science
technical report
Issue Date: Sep-1986
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-784
Abstract: In computer science the efficiency of algorithms is usually measured in terms of the size of the input. The output size, on the other hand, has been used for this purpose rather infrequently, except in certain enumerative query problems. This thesis deals with several constructive (in constrast to query) problems in computational geometry and presents algorithms whose running time depends non-trivially on the output size. We present an algorithm that finds the convex hull on $n$ points in the plane in worst case time $O(n \log H)$, where $H$ is the number of points that turn out to be vertices of the convex hull. we examine the $d$-dimensional maximal vector problem and show that as long as $V$, the number of maximal vectors in a set, is not too large, these maximal vectors can be found in $O(n \log V)$. We present an algorithm for solving the planar convex subdivision overlay problem in time proportional to the combined input and output size. Finally we show that, after some preprocessing in the form of linear programs, $d$-dimensional convex hulls can be constructed at logarithmic cost per face.
URI: http://hdl.handle.net/1813/6624
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
86-784.pdf8.74 MBAdobe PDFView/Open
86-784.ps1.68 MBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us