COMPUTATIONAL ASPECTS OF HELLYS THEOREM AND ITS RELATIVES

This paper investigates computational aspects of the well-known convexity theorem due to Helly, which states that the existence of a point in the common intersection of n convex sets is guaranteed by the existence of points in the common intersection of each combination of d + 1 of these sets. Given an oracle which accepts d + 1 convex sets and either returns a point in their common intersection, or reports its non-existence, we give two algorithms which compute a point in the common intersection of n such sets. The first algorithm runs in O(n(d+1)T) time and O(n(d)) space, where T is the time required for a single call to the oracle. The second algorithm is a multi-stage variant of the first by which the space complexity may be reduced to O (n) at the expense of an increase in the time complexity by a factor independent of n. We also show how these algorithms may be adapted to construct Linear and spherical separators of a collection of sets, and to construct a translate of a given object which either contains, is contained by, or intersects a collection of convex sets.