Output-Size Sensitive Algorithms for Constructive Problems in Computational Geometry

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.