Complements of Finite Unions of Convex Sets

Finite unions of convex sets are a central object of study in discrete and computational geometry. In this paper we initiate a systematic study of complements of such unions – i.e., sets of the form S = R^d \ (∪ⁿ_i=1Ki), where Ki are convex sets. In the first part of the paper we study isolated points in S, whose number is related to the Betti numbers of ∪ⁿ_i=1Ki and to its non-convexity properties. We obtain upper bounds on the number of such points, which are sharp for n = 3 and significantly improve previous bounds of Lawrence and Morris (2009) for all n ≪ ²_d^d . In the second part of the paper we study coverings of S by well-behaved sets. We show that S can be covered by at most g(d, n) flats of different dimensions, in such a way that each x ∈ S is covered by a flat whose dimension equals the “local dimension” of S in the neighborhood of x. Furthermore, we determine the structure of a minimum cover that satisfies this property. Then, we study quantitative aspects of this minimum cover and obtain sharp upper bounds on its size in various settings.