Adaptive planar convex hull algorithm for a set of convex hulls

Abstra t. An adaptive algorithm is one whi h performan e an be expressed more pre isely than as a mere fun tion of the size of the input: output-sensitive algorithms are a spe ial ase of adaptive algorithms. We onsider the omputation of the onvex hull of a set of onvex hulls, for instan e in the ase where the set of points has been omposed from simpler obje ts from a library, for ea h of whi h the onvex hull has been pre omputed. We show that in this ontext an adaptive algorithm performs better if it takes advantage of other features than the size of the output