HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

An Output-Sensitive Convex Hull Algorithm for Planar Objects

Franck Nielsen 1 Mariette Yvinec
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
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 \mbox{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 {\em bridge}, i.e. a facet of the convex 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 $\Theta (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 $\Theta (n\log h)$-time algorithm to compute the upper envelope of line segments.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:32:18 PM
Last modification on : Friday, February 4, 2022 - 3:17:59 AM
Long-term archiving on: : Thursday, March 24, 2011 - 2:14:29 PM


  • HAL Id : inria-00074107, version 1



Franck Nielsen, Mariette Yvinec. An Output-Sensitive Convex Hull Algorithm for Planar Objects. RR-2575, INRIA. 1995. ⟨inria-00074107⟩



Record views


Files downloads