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 = ℝᵈ ⧵ (∪₈=₁ⁿ Kᵢ), where Kᵢ 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 ∪₈=₁ⁿ Kᵢ 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 ≪ 2ᵈ/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.