2026-09-05T11:58:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25868 2026-06-23T12:59:55Z ddc:004 open_access

Complements of Finite Unions of Convex Sets Keller, Chaya Perles, Micha A. convexity 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 = ℝ^d ⧵ (∪_{i=1}^n K_i), where K_i 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=1}^n K_i 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/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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chaya Keller and Micha A. Perles 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.61 urn:nbn:de:0030-drops-258684 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.61 eng https://creativecommons.org/licenses/by/4.0/legalcode