Paper: Output-Sensitive Convex Hull Algorithms of Planar Convex Objects

Output-Sensitive Convex Hull Algorithms of Planar Convex Objects

Frank Nielsen and Mariette Yvinec

Some examples of convex hulls of a set of n ellipses (output-sensitive algorithm in O(nβ(h,4) log h) depending on h is the number of straight edges)

>(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.

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.