Abstract
One useful generalization of the convex hull of a set S of points is the ε-strongly convex δ-hull . It is defined to be a convex polygon Rgr; with vertices taken from S such that no point in S lies farther than δ outside Rgr; and such that even if the vertices of Rgr; are perturbed by as much as ε , Rgr; remains convex. It was an open question as to whether an ε -strongly convex ( ε )-hull existed for all positive ε . We give here an ( n log n ) algorithm for constructing it (which thus proves its existence). This algorithm uses exact rational arithmetic. We also show how to construct an ε-strongly convex ( ε + μ )-hull in ( n log n ) time using rounded arithmetic with rounding unit μ . This is the first rounded arithmetic convex hull algorithm which guarantees a convex output and which has error independent of n .
