Output-Sensitive Convex Hull Algorithms of Planar Convex Objects

Frank Nielsen and Mariette Yvinec

Some examples of convex hulls of a set of n disks (output-sensitive algorithm in O(nlog h) where h is the number of straight edges)
(pdf) (pdf) (pdf) (pdf) (pdf)
Abstract:
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.
 
Key words: computational geometry, convex hull, upper envelope, output-sensitive algorithms, marriage before conquest.
Download the PS paper © World Scientific Publishing (665 KB size, 28 pages, 8 figures).
 
The original publication is available at World Scientific.
 
The contents is also available in a technical report or in the Ph. D. thesis available online.
Bibtex entry:

@Article{ny-oschapco-1998,
    author = "Frank Nielsen and Mariette Yvinec",
    title = "Output-Sensitive Convex Hull Algorithms of Planar Convex Objects",
    journal = "International Journal of Computational Geometry and Applications",
    volume = "8",
    number = "1",
    pages = "39-66",
    year = "1998",
    doi="10.1142/S0218195998000047"
    }
Last updated, 2020.