AN OUTPUT-SENSITIVE CONVEX-HULL ALGORITHM FOR PLANAR OBJECTS

A set of planar objects is said to be of type m if the convex hull of any two objects has its size bounded by 2m. In this paper, we present an algorithm based on the marriage-before-conquest paradigm to compute the convex hull of a set of n planar convex objects of fixed type m. The algorithm is output-sensitive, i.e. its time complexity depends on the size h of the computed convex hull. The main ingredient of this a lgorithm is a linear method to find a bridge, i.e. a facet of the conv ex hull intersected by a given line. We obtain an O(n beta(h, m) log h )-time convex hull algorithm for planar objects. Here beta(h, 2) = O(1 ) and beta(h, m) is an extremely slowly growing function. As a direct consequence, we can compute in optimal O(n log h) time the convex hull of disks, convex homothets, non-overlapping objects. The method descr ibed in this paper also applies to compute lower envelopes of function s. In particular, we obtain an optimal -(n log h)-time algorithm to co mpute the upper envelope of line segments.