An Output-Sensitive Convex Hull Algorithm for Planar Objects
Frank Nielsen, Mariette Yvinec · International Journal of Computational Geometry & Applications · 1998
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 algorithm is a linear method to find a bridge, i.e. a facet of the convex hull intersected by a given line. We obtain an O(nβ(h,m log h)-time convex hull algorithm for planar objects. Here β(h,2)=O(1) and β(h,m) is an extremely slowly growing function. As a direct consequence, we can compute in optimal Θ(n log h) time the convex hull of disks, convex homothets, non-overlapping objects. The method described in this paper also applies to compute lower envelopes of functions. In particular, we obtain an optimal Θ(n log h)-time algorithm to compute the upper envelope of line segments.