Self-improving algorithms for convex hulls

Abstract

We describe an algorithm for computing planar convex hulls in the self-improving model: given a sequence I1, I2, . . . of planar n-point sets, the upper convex hull conv(I) of each set I is desired. We assume that there exists a probability distribution D on n-point sets, such that the inputs Ij are drawn independently according to D. Furthermore, D is such that the individual points are distributed independently of each other. In other words, the i'th point is distributed according to Di. The Di's can be arbitrary but are independent of each other. The distribution D is not known to the algorithm in advance. After a learning phase of nε rounds, the expected time to compute conv(I) is O(n + H(conv(I))). Here, H(conv(I)) is the entropy of the output, which is a lower bound for the expected running time of any algebraic computation tree that computes the convex hull. (More precisely, H(conv(I)) is the minimum entropy of any random variable that maps I to a description of conv(I) and to a labeling scheme that proves nonextremality for every point in I not on the hull.) Our algorithm is thus asymptotically optimal for D. Copyright © by SIAM.