Complements of Finite Unions of Convex Sets

Keller, Chaya; Perles, Micha A.

doi:10.4230/LIPIcs.SoCG.2026.61

Complements of Finite Unions of Convex Sets

Chaya Keller

School of Computer Science, Ariel University, Israel Micha A. Perles Einstein Institute of Mathematics, Hebrew University, Jerusalem, Israel

Abstract

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=\mathbb{R}^{d}\setminus(\cup_{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 $\cup_{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\ll\frac{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\in 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.

Keywords and phrases:

convexity, unions of convex sets

Funding:

Chaya Keller: Partially supported by Grant 1065/20 from the Israel Science Foundation.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The complexity of finite unions of convex sets has been a prolific research area in the last decades, due to intrinsic deep discrete-geometric questions pertaining to it and to applications to optimization, robotics, motion planning and other areas (see, e.g., the survey [1]). In some of these questions and applications, the structure of the complement plays an important role, and as a result, various structural questions regarding complements of such finite unions were studied in different works over the years.

One well-studied question is determining the maximum possible number of bounded connected components in $S=\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ (also known as voids in $K=\cup_{i=1}^{n}K_{i}$ ), where $\{K_{i}\}$ are convex. Asked by Fejes Tóth in the plane, and independently by Vitushkin (1958) in $\mathbb{R}^{d}$ , this question was studied both in full generality and for specific families of convex sets, such as translates of the same convex set (see, e.g., [2, 9]). As the number of voids is equal to the $(d-1)$ ’st Betti number of $\cup_{i=1}^{n}K_{i}$ , bounding its maximum size is the first step toward understanding the statistical behavior of the Betti numbers of such unions (see [8]).

A related question is determining the maximum possible number of all connected components (including unbounded ones). Kovalev [11] proved that the maximum is $\sum_{i=0}^{d}\binom{n}{i}$ , and that it is attained if and only if $K_{i}$ are either hyperplanes in general position, or layers between parallel hyperplanes. Bei, Chen and Zhang [5] provided a different proof, and applied the result to analyze the complexity of an algorithm they proposed for solving linear programming problems with only partial knowledge of the constraints.

In the case where $\{K_{i}\}$ are polyhedra, the combinatorial complexity of $S$ plays an important role in motion planning, and was studied, e.g., by Aronov and Sharir in [3, 4].

The case where $S$ is finite was studied by Lawrence and Morris [12], who obtained upper bounds on $|S|$ (which, in this case, is equal to the number of one-point holes in $K$ ) in terms of $n$ . As was shown much earlier by Matoušek and Valtr [13, Thm. 1.1(ii)], bounds on the number of one-point holes allow bounding the convexity number of $K$ in terms of its invisibility number (see also [7, Theorem 1]).

In this paper we initiate a systematic study of the structural properties of such sets $S$ . We concentrate on two types of questions – isolated points in $S$ (which were studied in the special case where $S$ is finite by Lawrence and Morris [12]), and covering of $S$ by flats (i.e., affine subspaces of $\mathbb{R}^{d}$ ).

Isolated points in $𝑺$ .

For the sake of convenience, we use the following definition:

Definition 1.

A point $p\in\mathbb{R}^{d}$ is encapsulated by the convex sets $K_{1},\ldots,K_{n}\subset\mathbb{R}^{d}$ if for some $\epsilon>0$ , $B(p,\epsilon)\setminus(\cup_{i=1}^{n}K_{i})=\{p\}$ , where $B(p,\epsilon)$ is the open ball of radius $\epsilon$ centered at $p$ . In other words, $p\in\mathbb{R}^{d}$ is encapsulated by $K_{1},\ldots,K_{n}\subset\mathbb{R}^{d}$ if these convex sets cover a pointed neighborhood of $p$ .

Lawrence and Morris [12] studied the case $|S|<\infty$ , in which every $p\in S$ is encapsulated by the convex sets $K_{1},\ldots,K_{n}$ . In the case where all $\{K_{i}\}$ are open, they used a classical theorem of Björner and Kalai [6] to show that $|S|\leq\binom{n-1}{d}$ . On the other hand they showed the existence of such a set $S$ with $(\lfloor\frac{n}{d}\rfloor-1)^{d}\leq|S|$ . With no additional assumption on $\{K_{i}\}$ (except for convexity), but assuming that $S$ affinely spans $\mathbb{R}^{d}$ , they obtained the upper bound $|S|\leq(n-1)(\binom{n}{\lfloor\frac{n}{2}\rfloor})^{d-1}$ .

We consider the general case, where no additional assumptions on $S$ and $\{K_{i}\}$ are made. First, we obtain the following tight bound on the number of points encapsulated by 3 convex sets:

Theorem 2.

Let $K_{1},K_{2},K_{3}\subset\mathbb{R}^{d}$ be 3 convex sets. Denote by $S$ the set of points of $\mathbb{R}^{d}$ encapsulated by $K_{1}\cup K_{2}\cup K_{3}$ . Define $f(d)=\lfloor\frac{3d}{2}\rfloor+1$ . Then:

(a) $|S|\leq f(d)$ ;

(b) If $|S|=f(d)$ then the sets $K_{1},K_{2},K_{3}$ are pairwise disjoint;

(c) The sets $K_{1},K_{2},K_{3}$ can be chosen in such a way that $|S|=f(d)$ and $\mathbb{R}^{d}\setminus(K_{1}\cup K_{2}\cup K_{3})=S$ .

For larger numbers of convex sets, let $f(d,n)$ be the maximal number of points that can be encapsulated by $n$ convex sets in $\mathbb{R}^{d}$ . It is easy to see¹¹1See also Theorem 9 below. that for $d\geq 1$ , $f(d,1)=0,f(d,2)=1$ , for all $n\geq 1$ we have $f(1,n)=n-1$ and by Theorem 2, $f(d,3)=\lfloor\frac{3d}{2}\rfloor+1$ . The following recursive bound can be proved inductively, by determining arbitrarily $f(0,n)=1$ .

Theorem 3.

For every $n>3,d\geq 2$ ,

f(d,n)\leq\sum_{i=2}^{n-1}\left(\binom{n}{i}f(d,i)\right)+f(d-2,n),

and consequently,

f(d,n)\leq 2d^{n-2}n!.

Note that for a constant $n$ , the bound we obtain is polynomial in $d$ , whereas the bound of [12] is exponential in $d$ . Furthermore, a direct calculation shows that our bound is superior as long as $n\ll\frac{2^{d}}{d}$ .

In addition, we prove a sharp bound in the plane, under the additional assumptions that $S$ is finite and the sets $K_{i}$ are pairwise disjoint. It turns out that while in $\mathbb{R}^{1}$ and for three sets in $\mathbb{R}^{2}$ , the maximal size of $S$ is obtained where the convex sets are pairwise disjoint, in the general case the disjointness assumption leads to a much smaller bound on $|S|$ – even in the plane, where the upper bound is linear in $n$ (compared to a quadratic lower bound without this restriction, see [10, Appendix A]).

Proposition 4.

Let $S=\mathbb{R}^{2}\setminus(\cup_{i=1}^{n}K_{i})$ where $n\geq 3$ and $\{K_{i}\}$ are pairwise disjoint convex sets. Assume that $|S|<\infty$ . Then $|S|\leq 5n-11$ , and this bound is sharp.

Covering $𝑺$ by flats.

For the sake of convenience, we use the following definition.

Definition 5.

For $S\subset\mathbb{R}^{d}$ , the flat-dimension of $S$ , $dm(S)$ , is

\operatorname{dm}(S)=\mbox{max}\{k:S\mbox{ includes a }k\mbox{-simplex}\},

where a $k$ -simplex (for $k\geq-1$ ) is the convex hull of $k+1$ affinely independent points in $\mathbb{R}^{d}$ .

The local dimension $\operatorname{dm}(S,p)$ of $S$ at $p\in S$ is

\operatorname{dm}(S,p)=\min_{\epsilon>0}\operatorname{dm}(S\cap B(p,\epsilon)).

Our main result in this part is the following theorem:

Theorem 6.

For any $n,d\in\mathbb{N}$ , there exists a number $g=g(n,d)$ such that the following holds. Let $S=\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ , where $\{K_{i}\}$ are convex sets. Then $S$ can be covered by at most $g$ flats, in such a way that each $p\in S$ is covered by a flat of dimension $\operatorname{dm}(S,p)$ . Furthermore, there exists a unique such cover $\mathcal{C}$ that is minimal with respect to inclusion.

Actually, the proof of Theorem 6 provides significant structural information on $\mathcal{C}$ : Suppose $p\in S,\operatorname{dm}(S,p)=k$ , and let $L$ be a flat. If $S\cap W=L\cap W$ for some neighborhood $W$ of $p$ , then $L$ is the $k$ -flat in $\mathcal{C}$ that covers $p$ .

On the quantitative side, the bound on $g(d,n)$ which follows from the proof is rather large, and in particular, the maximum numbers of flats of each dimension in $\mathcal{C}$ seem difficult to compute in general. Hence, we focus on special cases where effective bounds can be obtained. The following natural definition will be convenient.

Definition 7.

For $S=\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ , where $\{K_{i}\}$ are convex sets, and for $k=0,1,\ldots,d$ , denote by $\nu_{k}(S)$ the number of $k$ -flats in the cover $\mathcal{C}$ of $S$ . Denote by $\nu_{k}(d,n)$ the maximum of $\nu_{k}(S)$ over all such sets $S$ , where $d, n, k$ are fixed.

Theorems 2 and 3 above provide upper bounds on $\nu_{0}(d,n)$ (i.e., on the maximal number of $0$ -dimensional flats in $\mathcal{C}$ ), as by definition, the flat which covers each isolated point in $S$ must be the point itself. At the other end of the spectrum, it is clear that $\nu_{d}(d,n)=1$ . Regarding $(d-1)$ -flats, we determine $\nu_{d-1}(d,n)$ completely.

Theorem 8.

We have

\nu_{1}(2,n)=t(n,4)=(\tfrac{3}{4}+o(1))\binom{n}{2},\quad\mbox{and}\quad\nu_{d% -1}(d,n)=\binom{n}{2},\quad\forall d\geq 3,

where $t(n,4)$ is the Turán number.

Finally, in the case $n=2$ , i.e., where there are only two convex sets, we completely determine the numbers of $k$ -flats that can appear in the cover $\mathcal{C}$ of $S=\mathbb{R}^{d}\setminus(K_{1}\cup K_{2})$ , for each $0\leq k\leq d$ .

Theorem 9.

Let $K_{1},K_{2}$ be convex sets in $\mathbb{R}^{d}$ ( $d\geq 1$ ), and let $\mathcal{C}$ be the cover of $S=\mathbb{R}^{d}\setminus(K_{1}\cup K_{2})$ discussed above. Then any two flats $I,J\in\mathcal{C}$ satisfy $J\subset I$ or $I\subset J$ . Consequently, $\mathcal{C}$ contains at most one $k$ -flat for each $0\leq k\leq d$ .

Moreover, for any subset $T$ of $\{0,1,\ldots,d\}$ we can find $K_{1},K_{2}\subset\mathbb{R}^{d}$ such that $\mathcal{C}$ contains a $k$ -flat if and only if $k\in T$ .

The rest of the paper is organized as follows. In Section 2 we study isolated points in $S$ , proving Theorems 2 and 3. In Section 3 we study the qualitative question of covering $S$ by flats, proving Theorem 6. In Sections 4 and 5 we study quantitative aspects of covering $S$ by flats and present the proofs of Theorems 8 and 9.

2 Bounding the number of points encapsulated by convex sets

Recall that $f(d,n)$ is the maximal number of points that can be encapsulated by $n$ convex sets in $\mathbb{R}^{d}$ . It is easy to see that for every $n>0$ , $f(1,n)=n-1$ and that for every $d>0$ , $f(d,2)=1$ . After introducing a few definitions and an observation in Section 2.1, we determine $f(d,3)$ exactly in Section 2.2. Then, in Section 2.3 we obtain by an inductive argument an upper bound on $f(d,n)$ for $n>3$ .

2.1 Preliminaries

For a set $S\subset\mathbb{R}^{d}$ , denote by $\mbox{cl}(S)$ and $\mbox{int}(S)$ the topological closure and interior of $S$ , respectively. The convex hull of $S$ is denoted by $\mbox{conv}(S)$ . For $d\in\mathbb{N}$ and $0\leq k\leq d$ , a $k$ -flat $\pi\subset\mathbb{R}^{d}$ is a $k$ -dimensional affine subspace of $\mathbb{R}^{d}$ .

Definition 10.

For $K\subset\mathbb{R}^{d},p\in\mathbb{R}^{d}$ , we say that $p$ touches $K$ (or $K$ touches $p$ ), if $p\in\mbox{cl}(K)\setminus K$ .

The following observation will be used several times in the sequel.

Observation 11.

Let $K_{1},\ldots,K_{n}\subset\mathbb{R}^{d}$ be convex sets, and let $B$ be a $d$ -dimensional ball $B\subset K_{1}\cap\ldots\cap K_{n}$ . Let $p_{0}\notin K_{1}\cup\ldots\cup K_{n}$ . Consider the double cone with apex $p_{0}$ spanned by $B$ . Then the other side of this cone (the dark area in Figure 1) is disjoint to $K_{1},\ldots,K_{n}$ .

Indeed, for each $x$ in the other side of the cone above, $p_{0}$ lies inside a segment that connects $x$ to a point in each $K_{i}$ .

Figure 1: A cone with a vertex in

p_{0}

that is tangent to a ball

B

.

2.2 The number of points encapsulated by 3 convex sets in $\mathbb{R}^{d}$

The following theorem implies that $f(d,3)=\lfloor\frac{3d}{2}\rfloor+1$ . For the sake of simplicity, we denote by $S$ the set of encapsulated points, instead of the entire set $\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ . The reason for abusing notation is that in the proof of this theorem, elements of $\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ other than encapsulated points do not make any difference. Hence, we implicitly assume that there are no such elements, and thus, $\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ is equal to the set of encapsulated points.

Proof of Theorem 2.

We prove the first two statements together by induction on $d$ . The cases $d=0,1$ are trivial. For $d\geq 2$ and for every $p\in S$ , let

touch(p)=\{i:1\leq i\leq 3,\mbox{ and }p\mbox{ }touches\mbox{ }K_{i}\}.

We shall use the following observations.

Observation 12.

If $p$ is encapsulated by $K_{1},K_{2},K_{3}$ then $|touch(p)|\geq 2$ , and if $touch(p)=\{i,j\}$ then $K_{i}\cap K_{j}=\emptyset$ .

Indeed, if $q\in K_{i}\cap K_{j}$ then all the points on the line $\ell(p,q)$ that are separated from $q$ by $p$ , are not in $K_{i}\cup K_{j}$ . Since there exist such points arbitrarily close to $p$ , this contradicts the assumption on $p$ .

Observation 13.

If for $p\in S$ , $touch(p)=\{i,j\}$ then each of the cones $cone(p,K_{i})=\{(1-\lambda)p+\lambda x:\lambda>0,x\in K_{i}\},cone(p,K_{j})$ is a semi-space²²2In the plane, this means that each of $cone(p,K_{i}),cone(p,K_{j})$ is a half-open half-space. In general dimension, this means that there exists a unique orthonormal base $B=\{e_{1},\ldots,e_{d}\}$ of $\mathbb{R}^{d}$ such that with respect to $B$ , $cone(p,K_{i})$ is the set of all points that are lexicographically smaller than $p$ , and $cone(p,K_{j})$ is the set of all points that are lexicographically larger than $p$ .. Moreover, there is no other point $p^{\prime}\in S$ with $touch(p^{\prime})=\{i,j\}$ . (See Figure 2.)

Figure 2: An illustration for Observation 13 in

\mathbb{R}^{2}

where

touch(p)=\{i,j\}

. The set

K_{i}

is colored with red and

K_{j}

is colored with green. In this case

cone(K_{i})

is the upper half-plane, and

cone(K_{j})

is the lower half-plane.

By Observation 13, there is at most one point $p_{12}\in S$ with $touch(p_{12})=\{1,2\}$ , at most one point $p_{13}\in S$ with $touch(p_{13})=\{1,3\}$ , and at most one point $p_{23}\in S$ with $touch(p_{23})=\{2,3\}$ . By Observation 12, all other points in $S$ touch all three convex sets $K_{1},K_{2},K_{3}$ . Let $S^{\prime}=\{p\in S:|touch(p)|=3\}$ and let $J=\mbox{aff}(S^{\prime})$ be the flat spanned by $S^{\prime}$ . If $S^{\prime}=J=\emptyset$ then we are done. Otherwise, by Observation 11, $J$ cannot contain a $d$ -dimensional ball, and hence, $\mbox{dim}(J)<d$ .

Consider $S\cap J$ . This set includes $S^{\prime}$ and maybe some of the points $p_{ij}$ defined above. Every point in $S\cap J$ is encapsulated (w.r.t. $J$ ) by the three convex sets $K_{i}\cap J$ ( $1\leq i\leq 3$ ). Hence, by the induction hypothesis, $|S\cap J|\leq f(\dim(J))$ . There are 3 cases:

Case 1: $\dim(J)=d-2$ .

Then $|S^{\prime}|\leq f(d-2)$ , and since $S$ contains at most three points that are not in $S^{\prime}$ (i.e., the $p_{ij}$ ’s above), we have

|S|\leq|S^{\prime}|+3\leq f(d-2)+3=f(d).

If all inequalities hold with equality, then all three points $p_{12},p_{13}$ and $p_{23}$ exist, and by Observation 12, the $K_{i}$ ’s are pairwise disjoint.

Case 2: $\dim(J)<d-2$ .

Then

|S|\leq|S^{\prime}|+3\leq f(\dim J)+3<f(d).

Case 3: $\dim(J)=d-1$ .

In this case we prove that the points $p_{12},p_{13}$ and $p_{23}$ (if exist) are in $J$ , and therefore, $|S|\leq f(d-1)<f(d)$ , and we are done.

Indeed, assume to the contrary (w.l.o.g.) that $p_{12}$ exists and $p_{12}\notin J$ . Then $\dim(\mbox{conv}(S^{\prime}\cup\{p_{12}\}))=d$ . Moreover, since all the points in $S^{\prime}$ touch both $K_{1}$ and $K_{2}$ , we have

\mbox{conv}(S^{\prime}\cup\{p_{12}\})\subset\mbox{cl}(K_{1})\cap\mbox{cl}(K_{2% }).

Therefore, $\dim(\mbox{cl}(K_{1})\cap\mbox{cl}(K_{2}))=d$ , hence $K_{1}\cap K_{2}\neq\emptyset$ , in contradiction to Observation 12. This completes the proof of parts (a) and (b) of the theorem.

For the proof of (c) we need the following claim:

Claim 14.

Let $A,B\subset\mathbb{R}^{d}$ be convex sets such that $A\cap B=\emptyset$ , and let $z\in\mathbb{R}^{d}\setminus(A\cup B)$ . Then there exist two convex sets $\tilde{A},\tilde{B}\subset\mathbb{R}^{d}$ such that

$\blacksquare$

$A\subset\tilde{A},B\subset\tilde{B}$ ,
$\blacksquare$

$\tilde{A}\cap\tilde{B}=\emptyset$ , and
$\blacksquare$

$\tilde{A}\cup\tilde{B}=\mathbb{R}^{d}\setminus\{z\}$ ,

if and only if

A\cap(\mbox{conv}(B\cup\{z\}))=\emptyset\mbox{ and }B\cap(\mbox{conv}(A\cup\{z% \}))=\emptyset.

(1)

Proof of Claim 14.

The direction $(\Rightarrow)$ is trivial, since if (w.l.o.g.) $B\cap(\mbox{conv}(A\cup\{z\}))\neq\emptyset$ then there exist $a\in A$ and $b\in B$ such that $b$ in contained in the open segment $(a,z)$ . But in this case, no point on the opposite ray $\{(1+\lambda)z-\lambda a:\lambda>0\}$ can belong to $\tilde{A}$ or to $\tilde{B}$ , a contradiction.

For the opposite direction, assume for the sake of convenience that $z=0$ and that (1) is satisfied. An equivalent formulation of (1) is:

\mbox{Each ray from 0 meets at most one of the sets }A,B.

(2)

We shall now construct $\tilde{A}$ and $\tilde{B}$ . First, let $A^{+}=\bigcup_{\lambda>0}(\lambda A)$ (resp., $B^{+}=\bigcup_{\lambda>0}(\lambda B)$ ) be the union of all open rays from 0 via $A$ (resp., $B$ ). The sets $A^{+},B^{+}$ are convex and $A\subset A^{+},B\subset B^{+}$ . Since each ray from the origin intersects $A$ if and only if it intersects $A^{+}$ , and similarly for $B$ , the condition (2) is satisfied also for $A^{+},B^{+}$ . Therefore, $A^{+},B^{+}$ are disjoint convex sets that are closed under addition and multiplication by a positive scalar. Let

\mathcal{D}=\{F\subset\mathbb{R}^{d}\setminus\{0\}:F\mbox{ is closed under % addition and multiplication by a positive scalar}\},

and consider the family

\mathcal{F}=\{(A^{\prime},B^{\prime}):A^{\prime},B^{\prime}\in\mathcal{D},A^{% \prime}\cap B^{\prime}=\emptyset,A^{+}\subset A^{\prime},B^{+}\subset B^{% \prime}\}.

Define a partial order on $\mathcal{F}$ by $(A^{\prime},B^{\prime})\leq(A^{\prime\prime},B^{\prime\prime})$ iff $A^{\prime}\subseteq A^{\prime\prime}$ and $B^{\prime}\subseteq B^{\prime\prime}$ . Since each chain $\{(A^{\prime}_{i},B^{\prime}_{i})\}$ is bounded from above by $(\cup_{i}A^{\prime}_{i},\cup_{i}B^{\prime}_{i})$ , by Zorn’s lemma, $\mathcal{F}$ contains a maximal element $(\tilde{A},\tilde{B})$ . Clearly $\tilde{A},\tilde{B}$ are disjoint convex sets, $A\subset\tilde{A},B\subset\tilde{B}$ . It remains to prove that $\tilde{A}\cup\tilde{B}=\mathbb{R}^{d}\setminus\{0\}$ . Assume on the contrary that there exists a point $w\in\mathbb{R}^{d}\setminus(\tilde{A}\cup\tilde{B}\cup\{0\})$ . Then by the maximality of $(\tilde{A},\tilde{B})$ , the cone $\{\tilde{A}+\lambda w:\lambda>0\}$ meets $\tilde{B}\cup\{0\}$ . Therefore there exist $a\in\tilde{A}$ and $b^{\prime}\in\tilde{B}\cup\{0\}$ such that $w+a=b^{\prime}$ . Similarly, there exist $b\in\tilde{B}$ and $a^{\prime}\in\tilde{A}\cup\{0\}$ such that $w+b=a^{\prime}$ . Hence $b^{\prime}-a=a^{\prime}-b$ and it follows that $a+a^{\prime}=b+b^{\prime}\in\tilde{A}\cap\tilde{B}$ , a contradiction. This completes the proof of Claim 14. $\hfill\vartriangleleft$

Claim 14 implies the following consequence:

Corollary 15.

Let $H\subset\mathbb{R}^{d}$ be a $(k+1)$ -flat and let $J\subset H$ be a $k$ -flat. Let $A,B\subset J$ be disjoint convex sets. Assume that $J$ separates $H$ into two open half-flats $H^{+},H^{-}$ and that $z\in H^{+}$ . Then there exist two disjoint convex sets $\tilde{A},\tilde{B}$ such that $A\subset\tilde{A},B\subset\tilde{B}$ and $\tilde{A}\cup\tilde{B}=H\setminus\{z\}$ (see Figure 3). Moreover, the sets $\tilde{\tilde{A}}=(\tilde{A}\cap H^{+})\cup A,\tilde{\tilde{B}}=(\tilde{B}\cap H% ^{+})\cup B$ are disjoint convex sets such that $\tilde{\tilde{A}}\cap J=A,\tilde{\tilde{B}}\cap J=B$ and $(\tilde{\tilde{A}}\cup\tilde{\tilde{B}})\cap H^{+}=H^{+}\setminus\{z\}$ .

Figure 3: An illustration for Corollary 15 where

H=\mathbb{R}^{2}

and

J

is a line.

A

and

B

are two segments, as illustrated in the figure.

\tilde{B}

is the red half-open upper half-plane supported by

\ell

, and

\tilde{A}

is the blue half-open lower half-plane supported by

\ell

.

Now we are ready to prove part (c) of Theorem 2. We prove the construction by induction on $d$ . Given a construction in $\mathbb{R}^{d-2}$ of 3 convex sets that encapsulate $f(d-2)$ points, we extend each of the three convex sets to $\mathbb{R}^{d}$ in such a way that the previously encapsulated points are still encapsulated, and three more encapsulated points are formed. Since $f(d)=f(d-2)+3$ , such a construction completes the proof.

For the basic case, in $\mathbb{R}^{0}$ we can take $K_{1}=K_{2}=K_{3}=\emptyset$ , and in $\mathbb{R}^{1}$ the convex sets can be $K_{1}=(-\infty,0),K_{2}=(0,1)$ and $K_{3}=(1,\infty)$ . The construction for $d=2$ is illustrated in Figure 4 (though it can be also obtained by the inductive argument).

Figure 4: An illustration for the basic case

d=2

in the proof of Theorem 2(c).

In the induction step, let $J\subset\mathbb{R}^{d}$ be a $(d-2)$ -flat. By the induction hypothesis there exist three pairwise disjoint convex sets $K_{1}^{\prime},K_{2}^{\prime},K_{3}^{\prime}\subset J$ such that $|J\setminus(K_{1}^{\prime}\cup K_{2}^{\prime}\cup K_{3}^{\prime})|=f(d-2)$ . Let $\pi\subset\mathbb{R}^{d}$ be a plane orthogonal to $J$ , hence $\pi\cap J$ is a point. W.l.o.g., assume that $\pi\cap J=\{0\}$ . Consider 3 points $x_{1},x_{2},x_{3}\in\pi$ equally distributed around 0 (see Figure 5). Consider the $(d-1)$ -flat $H_{1}=\mbox{aff}(J,x_{1})$ , and let $H_{1}^{+}$ be the open half-flat of $H_{1}$ supported by $J$ that contains $x_{1}$ . (Formally, $H_{1}^{+}=\{y+\lambda x_{1}:y\in J,\lambda>0\}$ .) Define $H_{2}^{+},H_{3}^{+}$ similarly.

We are supposed to produce three pairwise disjoint convex sets ${K_{1}},{K_{2}},{K_{3}}$ , such that $K_{i}^{\prime}\subset{K_{i}}$ for $i=1,2,3$ and $\mathbb{R}^{d}\setminus({K_{1}}\cup{K_{2}}\cup{K_{3}})=J\setminus(K_{1}^{% \prime}\cup K_{2}^{\prime}\cup K_{3}^{\prime})\cup\{x_{1},x_{2},x_{3}\}$ . By Corollary 15, $K_{1}^{\prime}$ and $K_{2}^{\prime}$ can be extended to two disjoint convex sets $K_{1}^{3}$ and $K_{2}^{3}$ such that $K_{1}^{3}\cap J=K_{1}^{\prime}$ , $K_{2}^{3}\cap J=K_{2}^{\prime}$ and $K_{1}^{3}\cup K_{2}^{3}=K_{1}^{\prime}\cup K_{2}^{\prime}\cup H_{3}^{+}% \setminus\{x_{3}\}$ . Similarly, $K_{1}^{\prime}$ and $K_{3}^{\prime}$ can be extended to two disjoint convex sets $K_{1}^{2}$ and $K_{3}^{2}$ such that $K_{1}^{2}\cap J=K_{1}^{\prime}$ , $K_{3}^{2}\cap J=K_{3}^{\prime}$ and $K_{1}^{2}\cup K_{3}^{2}=K_{1}^{\prime}\cup K_{3}^{\prime}\cup H_{2}^{+}% \setminus\{x_{2}\}$ . $K_{2}^{1}$ and $K_{3}^{1}$ are obtained in the same way. Finally, we define ${K_{1}}=K_{1}^{2}\cup K_{1}^{3}\cup\mbox{int}(\mathrm{conv}(H_{2}^{+}\cup H_{3% }^{+}))$ and similarly, ${K_{2}}=K_{2}^{1}\cup K_{2}^{3}\cup\mbox{int}(\mathrm{conv}(H_{1}^{+}\cup H_{3% }^{+}))$ and ${K_{3}}=K_{3}^{1}\cup K_{3}^{2}\cup\mbox{int}(\mathrm{conv}(H_{1}^{+}\cup H_{2% }^{+}))$ . The sets ${K_{1}},{K_{2}}$ and ${K_{3}}$ encapsulate all the $f(d-2)$ points that were originally encapsulated by $K_{1}^{\prime},K_{2}^{\prime},K_{3}^{\prime}$ in $J$ , and additionally encapsulate $x_{1},x_{2},x_{3}$ . Therefore, we obtain $f(d-2)+3=f(d)$ points that are encapsulated by 3 convex sets in $\mathbb{R}^{d}$ . This completes the proof of part (c) of Theorem 2, and hence the proof of Theorem 2. $\hfill\blacktriangleleft$

Figure 5: An illustration for the induction step in the proof of Theorem 2(c).

2.3 The number of points encapsulated by $𝒏$ convex sets in $\mathbb{R}^{d}$

Recall that $f(d,n)$ is the maximal number of points that can be encapsulated by $n$ convex sets in $\mathbb{R}^{d}$ . Clearly³³3See also Theorem 9 below., for $d\geq 1$ , $f(d,1)=0,f(d,2)=1$ , and for all $n\geq 1$ we have $f(1,n)=n-1$ . Define arbitrarily $f(0,n)=1$ . After obtaining the value $f(d,3)=\lfloor\frac{3d}{2}\rfloor+1$ , the following theorem yields a recursive upper bound on the function $f(d,n)$ in general.

Theorem 3 (Restatement).

For every $n>3,d\geq 2$

f(d,n)\leq\sum_{i=2}^{n-1}\left(\binom{n}{i}f(d,i)\right)+f(d-2,n).

(3)

Consequently,

f(d,n)\leq 2d^{n-2}n!.

(4)

Proof.

The proof of the recursive formula is by a double induction on $n$ and $d$ , where the basic cases $f(1,n),f(d,2)$ and $f(d,3)$ have already been proved above. In the induction step, note that for each of the $\binom{n}{i}$ $i$ -subsets of $K_{1},\ldots,K_{n}$ , the points of $\mathbb{R}^{d}\setminus\bigcup_{i=1}^{n}K_{i}$ that touch exactly this subset, are encapsulated by this subset, and by the induction hypothesis their number is bounded by $f(d,i)$ . Therefore it remains to prove that the number of points that touch all $n$ sets is at most $f(d-2,n)$ .

Indeed, Let $S^{\prime}$ be the set of points that touch $K_{1},\ldots,K_{n}$ , and let $J=\mbox{aff}(S^{\prime})$ . By Observation 11, $\dim(J)<d$ . If $\dim(J)\leq d-2$ , we are done.

Otherwise, $\dim(J)=d-1$ . In this case, as in the argument of Case 3 in the proof of Theorem 2, no point that is encapsulated by some subset of $K_{1},\ldots,K_{n}$ lies outside $J$ . Indeed, otherwise there exists $T\subset[n]$ and a point $p\in\mathbb{R}^{d}\setminus J$ that touches each $K_{i}$ for $i\in T$ and no $K_{j}$ for $j\notin T$ . Then $\dim(\mathrm{conv}(S^{\prime}\cup\{p\}))=d$ , and since all the points in $S^{\prime}$ touch all the $K_{i}$ ’s for $i\in T$ , we have $\mathrm{conv}(S^{\prime}\cup\{p\})\subset\bigcap_{i\in T}\mbox{cl}(K_{i})$ , and $\bigcap_{i\in T}K_{i}$ is $d$ -dimensional. But then by Observation 11, $p$ is not encapsulated by $\bigcup_{i\in T}K_{i}$ .

Consequently, for every $T\subset[n]$ , all the points that are encapsulated by $\bigcup_{i\in T}K_{i}$ are in $J$ , and the bound $f(d-1,n)$ , which is smaller than the right hand side of (3) by the induction hypothesis on $d$ , follows.

The upper bound (4) follows from the recursive formula (3) by induction on $n$ , for every fixed $d\geq 2$ . The induction bases are the bounds $f(d,2)=1$ and $f(d,3)\leq\lfloor\frac{3d}{2}\rfloor+1\leq 2d$ , proved above. Assume that (4) holds for all $f(d,n^{\prime})$ , $n^{\prime}<n$ . Hence, by (3) we have

f(d,n)\leq\sum_{i=2}^{n-1}\left(\binom{n}{i}f(d,i)\right)+f(d-2,n)\leq\sum_{i=% 2}^{n-1}\left(\binom{n}{i}\cdot 2d^{i-2}i!\right)+2(d-2)^{n-2}n!.

Define $h_{d,n}(i)=\binom{n}{i}\cdot 2d^{i-2}i!$ . Note that for any $d\geq 2$ , $n\geq 4$ , $2\leq i\leq n-2$ ,

\frac{h_{d,n}(i+1)}{h_{d,n}(i)}=\frac{\binom{n}{i+1}\cdot 2d^{i-1}(i+1)!}{% \binom{n}{i}\cdot 2d^{i-2}i!}=\frac{n-i}{i+1}\cdot d(i+1)=(n-i)d\geq 2.

Hence, $\sum_{i=2}^{n-1}h_{d,n}(i)\leq 2h_{d,n}(n-1)$ . Thus, we have

	$\displaystyle f(d,n)$	$\displaystyle\leq\sum_{i=2}^{n-1}\left(\binom{n}{i}\cdot 2d^{i-2}i!\right)+2(d% -2)^{n-2}n!\leq 2nd^{n-3}(n-1)!+2(d-2)^{n-2}n!$
		$\displaystyle=2n!d^{n-2}\left(\tfrac{2}{d}+(\tfrac{d-2}{d})^{n-2}\right)\leq 2% n!d^{n-2}.$

This completes the proof of (4) by induction. $\hfill\blacktriangleleft$

We note that the upper bound (4) can be improved further with no much effort. However, it is not far from the best one can get from the recursion (3). Indeed, it is easy to see that for $n$ constant, the dependence on $d$ in (3) is $\Omega(d^{n-2})$ , and that for $d$ constant, the dependence on $n$ in (3) is super-exponential.

3 Covering the complement of finite unions of convex sets by flats

In this section we study covering of $S=\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ by flats – i.e., affine subspaces of $\mathbb{R}^{d}$ . The main result we prove is Theorem 6 which asserts that there exists a covering of $S$ by $g(n,d)$ flats such that any $p\in S$ is covered by a flat whose dimension is $\operatorname{dm}(S,p)$ .

3.1 Preliminaries

Recall that by Def. 5, the flat-dimension of $S$ is $\operatorname{dm}(S)=\mbox{max}\{k:S\mbox{ includes a }k\mbox{-simplex}\}$ , and the local dimension of $p\in S$ is $\operatorname{dm}(S,p)=\min_{\epsilon>0}\operatorname{dm}(S\cap B(p,\epsilon))$ .

Define $\operatorname{dm}(\emptyset)=-1$ . Note that $\operatorname{dm}(S)=0$ iff $S$ is non-empty, but does not include a non-degenerate straight line segment, and $\operatorname{dm}(S)=d$ iff $\mbox{int}(S)\neq\emptyset$ . Note that for general sets $S\subset\mathbb{R}^{d}$ , $\operatorname{dm}(S)$ does not necessarily coincides with the topological dimension of $S$ , nor with the dimension of its affine hull, $\mbox{dim}(\mbox{aff}(S))$ .

As for the local dimension, $\operatorname{dm}(S,p)=k$ if the intersection of $S$ with every neighborhood of $p$ includes a $k$ -simplex, but the intersection of $S$ with some neighborhood of $p$ does not include a $(k+1)$ -simplex. Refer to Figure 6 (and also to Figure 12 below) for an example of the local dimension. Note that if $\operatorname{dm}(S,p)=0$ then there exists some neighborhood $U$ of $p$ such that $S\cap U$ contains no segment. In this case $p$ is an isolated point of $S$ , since by Theorem 6, $S$ can be covered by finitely many points, hence $S\cap U$ is finite and therefore $p$ is isolated.

Figure 6: In the figure, the red-colored area is

S=\{(x,y):x<0\}\cup\{(x,0):x\geq 0\}=\mathbb{R}^{2}\setminus(K_{1}\cup K_{2})

, where

K_{1}=\{(x,y):x\geq 0,y>0\}

and

K_{2}=\{(x,y):x\geq 0,y<0\}

. In this case,

\operatorname{dm}(S,(0,0))=2

and

\operatorname{dm}(S,(1,0))=1

. The point

(1,0)

is an ordinary point of

S

(with the

x

-axis as the corresponding 1-flat), while

(0,0)

is not.

Ordinary points and ordinary flats.

Definition 16.

The point $p$ is a $k$ -ordinary point of $S$ ( $p\in S\subset\mathbb{R}^{d}$ ) if

1.

$\operatorname{dm}(S,p)=k.$
2.

For some $k$ -flat $H\subset\mathbb{R}^{d}$ and for some open neighborhood $U$ of $p$ , $S\cap U=H\cap U$ .

We call $H$ a $k$ -ordinary flat of $S$ . Moreover, $p$ is called an ordinary point of $S$ if it is $k$ -ordinary for some $0\leq k\leq d$ . Similarly for flats.

The set of $k$ -ordinary points of $S$ is a relatively open subset of $S$ . Indeed, if $p$ is a $k$ -ordinary point of $S$ and $U, H$ are as in Definition 16, then every point $x\in S\cap U$ is $k$ -ordinary as well with the same $k$ -flat $H$ . Note that if Definition 16 holds for $U$ then it clearly holds for any smaller neighborhood $p\in U^{\prime}\subset U$ . Moreover, the flat $H$ is determined by the point $p$ , $H=\mbox{aff}(U\cap S)$ , for an appropriate neighborhood $U$ as in Definition 16.

$\blacktriangleright$ Remark 17.

If $S^{\prime}$ is relatively open subset of $S$ , (i.e., $S^{\prime}=S\cap U$ where $U$ is an open subset of $\mathbb{R}^{d}$ ) then for every point $p\in S^{\prime}$ , $\operatorname{dm}(S,p)=\operatorname{dm}(S^{\prime},p)$ . Moreover, $p$ is a $k$ -ordinary point of $S$ iff it is a $k$ -ordinary point of $S^{\prime}$ (with the same $k$ -ordinary flat.)

Strong covers.

Definition 18.

Let $S\subset\mathbb{R}^{d}$ . A collection $\mathcal{C}$ of flats in $\mathbb{R}^{d}$ is a strong cover of $S$ , if:

1.

$|\mathcal{C}|<\infty$
2.

Each point $p\in S$ belongs to some $k$ -flat $H\in\mathcal{C}$ , where $k=\operatorname{dm}(S,p)$ .
3.

$\mathcal{C}$ is minimal, i.e., no proper subcollection of $\mathcal{C}$ satisfies (2).

3.2 Proof of Theorem 6

Our main result in this section is the following restatement of Theorem 6 (where the value of the function $g$ from the original statement follows from the proof).

Theorem 6 (Restatement).

Let $K_{1},\ldots,K_{n}$ be convex subsets of $\mathbb{R}^{d}$ and let $S=\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ . Then $S$ admits a unique strong cover $\mathcal{C}$ . Actually, $\mathcal{C}$ is the collection of all ordinary flats with respect to $S$ .

Note that $p$ is encapsulated by $K_{1},\ldots,K_{n}$ if and only if $\{p\}$ is an 0-ordinary flat w.r.t. $\mathbb{R}^{d}\setminus(K_{1}\cup\ldots\cup K_{n})$ . Hence, both Theorems 2 and 3 above, supply quantitative bounds for special cases of Theorem 6.

It is easy to see that any strong cover $\mathcal{C}$ of $S$ must contain all ordinary flats of $S$ . Indeed, given a $k$ -ordinary flat $H$ , there exists some $k$ -ordinary point $p\in S$ and some open neighborhood $U$ of $p$ , such that $S\cap U=H\cap U$ . If $H\notin\mathcal{C}$ then consider all the $k$ -flats $H^{\prime}\in\mathcal{C}$ . Since for any such $H^{\prime}$ , $H\neq H^{\prime}$ , it follows that $\mbox{dim}(H\cap H^{\prime})<k$ , therefore the neighborhood $U$ is not covered by these (finitely many) $k$ -flats $H^{\prime}$ . But as mentioned above, each point in $S\cap U$ is a $k$ -ordinary point of $S$ – a contradiction.

Therefore, in order to prove Theorem 6 we show that there are only finitely many ordinary flats with respect to $S$ , and that condition (2) of Definition 16 is satisfied not only for the ordinary points of $S$ (which is trivial), but also for the non-ordinary points of $S$ .

Proof of Theorem 6.

The proof is by a primary induction on $d$ and a secondary induction on $n$ . For the induction basis, let $p\in S\subset\mathbb{R}^{d}$ with $\operatorname{dm}(S,p)=k$ . If $k=d$ then no inductive argument is needed since $p\in\mbox{cl}(\mbox{int}(S))$ , and then the corresponding $d$ -flat is $\mathbb{R}^{d}$ . The case $d=0$ is trivial. If $d=1$ and $k=0$ then $p$ is an isolated point of $S$ and the number of such points $p$ is at most $n-1$ . The corresponding 0-flat in this case is clearly $\{p\}$ . If $d=1$ and $k=1$ then $\mathbb{R}^{1}$ is the corresponding 1-flat. If $n=1$ then for any $p\in S$ , $\operatorname{dm}(S,p)=d$ and $\mathbb{R}^{d}$ is the $d$ -ordinary flat.

For larger values of $n$ and $d$ we shall prove by induction the following:

1.

For any $0\leq k\leq d$ , there are finitely many $k$ -ordinary flats w.r.t. $S$ .
2.

For any $p\in S$ with $\operatorname{dm}(S,p)=k$ and for any $\epsilon>0$ , there is a $k$ -ordinary point $q\in S$ such that $||p-q||<\epsilon$ .

$\blacktriangleright$ Remark 19.

The second statement implies the existence of a $k$ -ordinary flat $J$ such that $p\in J$ . Indeed, by the statement $p$ is in the closure of the $k$ -ordinary points of $S$ , each of which is contained in a $k$ -ordinary flat. But these flats form a closed set, hence $p$ is contained in at least one of these $k$ -ordinary flats.

The sets to which we apply the induction hypothesis are as follows:

$\blacksquare$

$S^{i}=\mathbb{R}^{d}\setminus\bigcup_{j\neq i}K_{j}$ , ( $i=1,2,\ldots,n$ ), to which we apply the induction hypothesis with the same $d$ and $n-1$ convex sets.
$\blacksquare$

For a flat $H$ (to be specified later) with $\mbox{dim}(H)<d$ , consider $S^{H}=H\setminus(\bigcup_{j=1}^{n}(K_{j}\cap H))$ , that is, the restriction⁴⁴4Note that along the proof, when considering $S^{H}$ , we treat $S^{H}$ as a subset of $H$ (and not as a subset of $\mathbb{R}^{d}$ ). of the original system to $H$ . Here we apply the induction hypothesis with the dimension $\mbox{dim}(H)$ .

We will prove that any $k$ -ordinary flat w.r.t. $S$ is either a $k$ -ordinary flat w.r.t. some $S^{i}$ or a $k$ -ordinary flat for some $S^{H}$ with $\mbox{dim}(H)<d$ . Hence we will be able to apply the induction hypothesis either to $S^{i}$ or to $S^{H}$ .

Let $p\in S$ with $\operatorname{dm}(S,p)=k$ . There are two options:

$\blacksquare$

Case 1: For some $1\leq i\leq n$ , $p$ does not touch $K_{i}$ .
$\blacksquare$

Case 2: $p$ touches all sets $K_{i}$ , $1\leq i\leq n$ .

We handle each case separately.

Case 1:

Since $p$ does not touch $K_{i}$ , it follows that $p\in\mbox{int}(\mathbb{R}^{d}\setminus K_{i})$ , and thus, $p$ has a positive distance from $K_{i}$ . Let $U$ be a neighborhood of $p$ in $\mathbb{R}^{d}$ that satisfies $U\subset\mbox{int}(\mathbb{R}^{d}\setminus K_{i})$ . Then $S\cap U=S^{i}\cap U$ and $\operatorname{dm}(S^{i},p)=\operatorname{dm}(S,p)=k$ . Moreover, for every corresponding $k$ -flat $J$ with $J\cap U=S\cap U$ we have $J\cap U=S^{i}\cap U$ . Hence, the set of $k$ -ordinary flats w.r.t. $S$ that correspond to a point $p$ as in case 1, is included in the union of the sets of $k$ -ordinary flats w.r.t. $S^{i}$ , $1\leq i\leq n$ , and we are done by the induction hypothesis on the $S^{i}$ ’s.

Case 2:

Let $G=\{p\in S:p\mbox{ touches all }K_{i}\mbox{'s}\}$ and let $H=\mbox{aff}(G)$ be the flat that is spanned by $G$ . If $H=\mathbb{R}^{d}$ then $\mbox{conv}(G)$ is $d$ -dimensional and $\mbox{int(conv}(G))\subset\bigcap_{1\leq i\leq n}K_{i}$ . Then $\operatorname{dm}(p,S)=d$ holds for all $p\in G$ , and the corresponding $d$ -flat is $\mathbb{R}^{d}$ . From now on we assume $\mbox{dim}(H)<d$ .

Clearly $\operatorname{dm}(S^{H},p)\leq k$ , and every neighborhood of $p$ in $S$ includes a $k$ -simplex. We distinguish between two cases:

Case 2a: Any neighborhood $𝑼$ of $𝒑$ includes a $𝒌$ -simplex that is not included in $𝑯$ .

In this case, in each sufficiently small neighborhood $U=B(p,\frac{1}{m})$ of $p$ we can find a point $q_{m}$ with $\operatorname{dm}(S,q_{m})=k$ and $q_{m}\notin H$ . By the definition of $H$ , this means that for some $1\leq i\leq n$ , $q_{m}$ does not touch $K_{i}$ . By passing to a subsequence $\{q_{m_{r}}\}_{r=1}^{\infty}$ we can assume that for a fixed $1\leq i\leq n$ , each $q_{m_{r}}$ does not touch $K_{i}$ . By the induction hypothesis on $S^{i}$ , each $q_{m_{r}}$ is contained in a $k$ -ordinary flat w.r.t. $S^{i}$ , where the number of such flats is finite. By passing again to a subsequence, we can restrict ourselves to only one such $k$ -ordinary flat, $J$ . Therefore, we obtain in this flat a sequence of $k$ -ordinary points that tend to $p$ and by the closedness of $J$ , $p\in J$ .

Case 2b: There exists a neighborhood $𝑼$ of $𝒑$ such that every $𝒌$ -simplex in $S\cap U$ is contained in $𝑯$ .

In this case, $\operatorname{dm}(S^{H},p)=k$ and we can apply the induction hypothesis to $S^{H}$ , since we have already assumed $\mbox{dim}(H)<d$ . By this induction hypothesis there exists a $k$ -ordinary flat $J^{\prime}$ (w.r.t $S^{H}$ ) that contains $p$ , and a sequence of $k$ -ordinary points in $J^{\prime}\cap S^{H}$ that tends to $p$ .

The only thing that is left to prove is that $J^{\prime}$ is ordinary not only w.r.t. $S^{H}\subset H$ but also w.r.t. $S\subset\mathbb{R}^{d}$ . Indeed, let $U^{\prime}\subset U$ be a neighborhood of $p$ such that $U^{\prime}\cap J^{\prime}=U^{\prime}\cap S^{H}$ . If some point $q\in U^{\prime}$ is the limit of a sequence of points from $S$ outside $H$ , each point in the sequence does not touch some $K_{i}$ , and by passing to a subsequence, we can assume that all its elements do not touch $K_{i}$ for a fixed $i$ . Then, by the induction hypothesis on $S^{i}$ , the whole sequence is contained in finitely many $(\leq k)$ -flats, none of them is $J^{\prime}$ . The union of all these $(\leq k)$ -flats, intersects $J^{\prime}$ in a $(<k)$ -dimensional set, hence we can find $U^{\prime\prime}\subset U^{\prime}$ s.t. $U^{\prime\prime}\cap J^{\prime}=U^{\prime\prime}\cap S$ , namely, $J^{\prime}$ is $k$ -ordinary also w.r.t. $S$ . $\hfill\blacktriangleleft$

4 Bounding the number of ordinary hyperplanes

In this section we present the proof of Theorem 8 which essentially determines the maximal possible number of hyperplanes in the strong cover $\mathcal{C}$ of $S=\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ , whose existence was proved in Theorem 6. In Theorem 20 we prove the assertion of the theorem for $d\geq 3$ , and in Theorem 21 we prove it for $d=2$ . We formulate these theorems using the notion of ordinary hyperplanes, whose number is equal, by the proof of Theorem 6, to the notion $\nu_{d-1}$ used in the formulation of Theorem 8.

Theorem 20.

Let $d\geq 3$ and let $S=\mathbb{R}^{d}\setminus(\cup_{i=1}^{n}K_{i})$ , where $\{K_{i}\}$ are convex sets. Then the number of ordinary hyperplanes (i.e., $(d-1)$ -flats) w.r.t. $S$ is at most $\binom{n}{2}$ . On the other hand, the value $\binom{n}{2}$ is attained for some $K_{1},\ldots,K_{n}$ .

Due to space limit, the proof is presented in [10, Theorem 4.1].

In the case $d=2$ , we prove an upper bound of $(\frac{3}{4}+o(1))\binom{n}{2}$ , and provide a construction for which this value is obtained.

Theorem 21.

Let $S=\mathbb{R}^{2}\setminus(\cup_{i=1}^{n}K_{i})$ , where $\{K_{i}\}$ are convex sets. Then the maximum possible number of ordinary lines w.r.t. $S$ is the Turán number $t(n,4)=(\tfrac{3}{4}+o(1))\binom{n}{2}$ . On the other hand, this value is attained for some $K_{1},\ldots,K_{n}$ .

Proof.

For the upper bound we consider the geometric graph $G$ , whose vertices are $n$ arbitrary points $x_{i}\in\mbox{int}(K_{i})$ ( $1\leq i\leq n,\forall i\neq j:x_{i}\neq x_{j}$ ), and whose edges are defined as follows: For each ordinary line $\ell$ that corresponds to a 1-ordinary point $p_{\ell}$ , there exist (as in the proof of Theorem 20) $K_{i},K_{j}$ with $\dim K_{i}=\dim K_{j}=2$ , such that $\ell$ is the only line that weakly separates $K_{i}$ and $K_{j}$ , $p\in\mbox{cl}{(K_{i})}\cap\mbox{cl}({K_{j}})$ . (Clearly, $\mbox{int}(K_{i})\cap\mbox{int}(K_{j})=\emptyset$ .) We connect $x_{i}$ to $x_{j}$ in $G$ by a two-edges polygonal path $[x_{i},p_{\ell},x_{j}]$ .

By the disjointness of $\mbox{int}(K_{i})$ and $\mbox{int}(K_{j})$ , the graph $G$ (though not necessarily planar) does not include $K_{5}$ , since otherwise there exist 5 pairwise disjoint open convex sets whose closures are pairwise intersecting, which is impossible since the restriction of $G$ to the corresponding vertices is planar by the disjointness of the 5 $\mbox{int}(K_{i})$ ’s. Hence, by Turán’s Theorem, $|E(G)|\leq t(n,4)=(\frac{3}{4}+o(1))\binom{n}{2}$ , and the upper bound on the number of ordinary lines follows.

On the other hand, we present a construction that realizes every complete 4-partite graph $K_{n_{1},n_{2},n_{3},n_{4}}$ with $n_{1}+n_{2}+n_{3}+n_{4}=n$ , in particular Turán’s graph. The construction is a bit complicated, hence we present it in five steps accompanied by illustrations.

Step 1.

First consider four closed convex sets $K_{1},K_{2},K_{3},K_{4}$ as in Figure 7. Let $e_{ij}=K_{i}\cap K_{j}$ for $1\leq i<j\leq 4$ . Each segment $e_{ij}$ on the line that separates $K_{i}$ from $K_{j}$ .

Figure 7: An illustration for step 1 in the proof of Theorem 21.

Our goal is to construct for each $1\leq i\leq 4$ , $n_{i}$ open convex sets $K_{i}^{1},\ldots,K_{i}^{n_{i}}$ , each of which is a subset of a tiny perturbation of $K_{i}$ . This construction has the property that for every $1\leq i<j\leq 4$ , and for every $1\leq\ell_{i}\leq n_{i},1\leq\ell_{j}\leq n_{j}$ , there exists an ordinary line separating $K_{i}^{\ell_{i}}$ from $K_{j}^{\ell_{j}}$ . By taking the $n_{i}$ ’s ( $1\leq i\leq 4$ ) as equal as possible and satisfying $n_{1}+n_{2}+n_{3}+n_{4}=n$ , we obtain in this way $n$ convex sets with $\Sigma_{i<j}n_{i}n_{j}=t(n,4)$ ordinary lines as asserted.

Step 2.

For every $1\leq i<j\leq 4$ , draw a circular arc $\gamma_{ij}$ through the endpoints of $e_{ij}$ inside $K_{i}$ (see Figure 8).

Figure 8: An illustration for step 2 in the proof of Theorem 21.

The radius of the circle associated with this arc, should be very large (in a sense to be clarified later). Note that in Figures 8-11 this radius is not large enough, just to make the illustration easier to follow.

Step 3.

For every $1\leq i<j\leq 4$ , split $\gamma_{ij}$ by $n_{i}+1$ points into $n_{i}+2$ parts. Let the edges of the polygonal path through these points (and the endpoints of $e_{ij}$ ) be $a_{0}^{ij},a_{1}^{ij},\ldots,a_{n_{i}+1}^{ij}$ . See Figure 9, in which the polygonal paths corresponding to $\gamma_{12},\gamma_{23}$ and $\gamma_{24}$ are illustrated. In this figure, $n_{1}=2$ and $n_{2}=3$ .

Figure 9: An illustration for step 3 in the proof of Theorem 21. Here

n_{1}=2,n_{2}=3

.

Step 4.

For every $1\leq i<j\leq 4$ , and $1\leq t\leq n_{i}$ , draw an arc $\delta_{t}^{ij}$ through the endpoints of $a_{t}^{ij}$ to the side of $K_{j}$ . Again, the radius of the circle associated with $\delta_{t}^{ij}$ should be very large (as will be determined later), much larger than in Figure 10 (in which still $n_{1}=2$ and $n_{2}=3$ ).

Figure 10: An illustration for step 4 in the proof of Theorem 21. Here

n_{1}=n_{3}=n_{4}=2,n_{2}=3

.

Partition $\delta_{t}^{ij}$ into $n_{j}+2$ sub-arcs by adding $n_{j}+1$ points on it, and let the edges of the polygonal path through these points (and the endpoints of $a_{t}^{ij}$ ) be $b_{t,0}^{ij}\ldots,b_{t,n_{j}+1}^{ij}$ . In Figure 11, these polygonal paths are illustrated, where $n_{1}=n_{3}=n_{4}=2$ , and $n_{2}=3$ .

Figure 11: An illustration for steps 4-5 in the proof of Theorem 21. Here

n_{1}=n_{3}=n_{4}=2,n_{2}=3

.

Step 5.

Let $1\leq i\leq 4$ . In this step we construct $n_{i}$ open convex sets $K_{i}^{1},\ldots,K_{i}^{n_{i}}$ , each of which is a subset of a tiny perturbation of $K_{i}$ . Each of these $n_{i}$ convex sets will be the interior of the convex hull of several segments, and the radii of the circles mentioned in steps 2 and 4 should be so large, such that all the segments that are involved in the construction of each $K_{i}^{\ell}$ ( $1\leq\ell\leq n_{i}$ ) will be on the boundary of $\mbox{cl}(K_{i}^{\ell})$ . Note that each $K_{i}^{\ell}$ is an open convex polygon⁵⁵5This is the reason why in the construction we omit the first and the last segments of each arc..

The first such set, $K_{i}^{1}$ , is the interior of the convex hull of the following segments:

\begin{cases}b_{1,1}^{ij},b_{2,1}^{ij},\ldots b_{n_{j},1}^{ij}&:1\leq j<i\\ b_{1,1}^{ij},b_{1,2}^{ij},\ldots b_{1,n_{j}}^{ij}&:i<j\leq 4\end{cases}

In Figure 11 (that still demonstrates the case where $n_{1}=2,n_{2}=3$ ), the segments that form $K_{2}^{1}$ are colored black. Roughly speaking, from the arcs inside $K_{i}$ we take consecutive “ $b$ ” edges whose endpoints lie on the first “ $\delta$ ”-arc corresponding to each edge of $K_{i}$ , and from the arcs out of $K_{i}$ that correspond to an edge of $K_{i}$ , we take the first “ $b$ ”-edge from each “ $\delta$ ”-arc. Recall that the radii of all arcs involved are so large, that (unlike the drawing in Figures 8 -11) all these “ $b$ ”-edges that form each $K_{i}^{\ell}$ are in convex position.

The second such set, $K_{i}^{2}$ , is the interior of the convex hull of the following segments, colored by green in Figure 11:

\begin{cases}b_{1,2}^{ij},b_{2,2}^{ij},\ldots b_{n_{j},2}^{ij}&:1\leq j<i\\ b_{2,1}^{ij},b_{2,2}^{ij},\ldots b_{2,n_{j}}^{ij}&:i<j\leq 4\end{cases}

In general, for each $1\leq\ell\leq n_{i}$ , the set $K_{i}^{\ell}$ is the interior of the convex hull of the following segments:

\begin{cases}b_{1,\ell}^{ij},b_{2,\ell}^{ij},\ldots b_{n_{j},\ell}^{ij}&:1\leq j% <i\\ b_{\ell,1}^{ij},b_{\ell,2}^{ij},\ldots b_{\ell,n_{j}}^{ij}&:i<j\leq 4\end{cases}

In this way, as was mentioned just after Step 1, we construct $n$ open convex sets with $\Sigma_{i<j}n_{i}n_{j}$ distinct ordinary lines. This completes the proof of Theorem 21. $\hfill\blacktriangleleft$

5 The complement of the union of two convex sets

In this section we present the proof of Theorem 9, which fully characterizes the set of possible vectors $(v_{0},\ldots,v_{d})$ attainable as the numbers of ordinary $k$ -flats of $S=\mathbb{R}^{d}\setminus(K_{1}\cup K_{2})$ , where $K_{1},K_{2}\subset\mathbb{R}^{d}$ are convex sets. The theorem follows immediately from Claims 22, 23 below.

A construction for $d=2$ , in which a strong cover of $S$ consists of exactly one $k$ -ordinary flat for every $0\leq k\leq d$ (or in other words, a construction which corresponds to the vector $(v_{0},v_{1},v_{2})=(1,1,1)$ ) is presented in Figure 12.

Figure 12: The circle in this figure is centered at the origin. The sets

K_{1}

and

K_{2}

are colored with red and green, respectively. The set

K_{1}

contains the left half circle (including its arc) and the segment

[(0,1),(0,-\frac{1}{3}))

, and

K_{2}

contains the quarter right-bottom circle and the segments

[(0,0),(1,0)]

and

((0,-\frac{1}{3}),(0,-\frac{2}{3})]

. The point

x\in S=\mathbb{R}^{2}\setminus(K_{1}\cup K_{2})

is of local dimension

d=2

and the corresponding 2-ordinary flat is

\mathbb{R}^{2}

. The point

y

is of local dimension

1

and the corresponding 1-ordinary flat is the

y

-axis. The point

z

is of local dimension

0

and the corresponding 0-ordinary flat is

\{z\}

itself.

The following claim implies that for every $0\leq k\leq d$ , a strong cover of $S$ contains at most one $k$ -ordinary flat.

Claim 22.

Let $K_{1},K_{2}\subset\mathbb{R}^{d}$ be convex sets, and let $S=\mathbb{R}^{d}\setminus(K_{1}\cup K_{2})$ . If $J_{1},J_{2}$ are $k$ -ordinary flats w.r.t. $S$ then $J_{1}\subset J_{2}$ or $J_{2}\subset J_{1}$ .

Due to space limit, the proof of Claim 22 is presented in [10, Claim 5.1].

On the other hand, for any subset $T$ of $\{0,1,\ldots,d\}$ we can find $K_{1},K_{2}\subset\mathbb{R}^{d}$ such that $\mathcal{C}$ contains a $k$ -flat if and only if $k\in T$ .

Claim 23.

Let $f:\{0,\ldots,d\}\rightarrow\{0,1\}$ . Then there exist convex sets $K_{1},K_{2}\subset\mathbb{R}^{d}$ such that the number of $k$ -ordinary flats in a strong cover of $S=\mathbb{R}^{d}\setminus(K_{1}\cup K_{2})$ is $f(k)$ .

The proof of Claim 23 is presented in [10, Claim 5.2].

References

[1] P. K. Agarwal, J. Pach, and M. Sharir. State of the union, of geometric objects: A review. In Proc. Joint Summer Research Conf. on Discrete and Computational Geometry: 20 Years Later, Contemp. Math. 452, pages 9–48. AMS, 2008.
[2] B. Aronov, O. Cheong, M. G. Dobbins, and X. Goaoc. The number of holes in the union of translates of a convex set in three dimensions. Discret. Comput. Geom., 57(1):104–124, 2017. doi:10.1007/S00454-016-9820-4.
[3] B. Aronov and M. Sharir. The common exterior of convex polygons in the plane. Comput. Geom., 8:139–149, 1997. doi:10.1016/S0925-7721(96)00004-1.
[4] B. Aronov and M. Sharir. On translational motion planning of a convex polyhedron in 3-space. SIAM J. Comput., 26(6):1785–1803, 1997. doi:10.1137/S0097539794266602.
[5] X. Bei, N. Chen, and S. Zhang. Solving linear programming with constraints unknown. In ICALP 2015, Part I, volume 9134 of Lecture Notes in Computer Science, pages 129–142. Springer, 2015. doi:10.1007/978-3-662-47672-7_11.
[6] A. Björner and G. Kalai. An extended Euler–Poincaré theorem. Acta Math., 161:279–303, 1988.
[7] J. Cibulka, M. Korbelář, J. Kynčl, V. Mészáros, R. Stolař, and P. Valtr. On three measures of non-convexity. Israel J. Math., 218:331–369, 2017.
[8] H. Edelsbrunner and J. Pach. Maximum Betti numbers of Čech complexes. In SoCG 2024, volume 293 of LIPIcs, pages 53:1–53:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.SOCG.2024.53.
[9] G. O. H. Katona. On a problem of L. Fejes Tóth. Stud. Sci. Math. Hung., 12(1–2):77–80, 1977.
[10] Chaya Keller and Micha A. Perles. Complements of finite unions of convex sets, arxiv:2508.19413, 2025. arXiv:2508.19413.
[11] M. D. Kovalev. A property of convex sets and its application. Mat. Zametki (in Russian), 44:89–99, 1988.
[12] J. Lawrence and W. D. Morris Jr. Finite sets as complements of finite unions of convex sets. Discret. Comput. Geom., 42(2):206–218, 2009. doi:10.1007/S00454-009-9184-0.
[13] J. Matoušek and P. Valtr. On visibility and covering by convex sets. Israel J. Math., 113(3):341–379, 1999.

[bib.bib1] [1] P. K. Agarwal, J. Pach, and M. Sharir. State of the union, of geometric objects: A review. In Proc. Joint Summer Research Conf. on Discrete and Computational Geometry: 20 Years Later, Contemp. Math. 452, pages 9–48. AMS, 2008.

[bib.bib2] [2] B. Aronov, O. Cheong, M. G. Dobbins, and X. Goaoc. The number of holes in the union of translates of a convex set in three dimensions. Discret. Comput. Geom., 57(1):104–124, 2017. doi:10.1007/S00454-016-9820-4.

[bib.bib3] [3] B. Aronov and M. Sharir. The common exterior of convex polygons in the plane. Comput. Geom., 8:139–149, 1997. doi:10.1016/S0925-7721(96)00004-1.

[bib.bib4] [4] B. Aronov and M. Sharir. On translational motion planning of a convex polyhedron in 3-space. SIAM J. Comput., 26(6):1785–1803, 1997. doi:10.1137/S0097539794266602.

[bib.bib5] [5] X. Bei, N. Chen, and S. Zhang. Solving linear programming with constraints unknown. In ICALP 2015, Part I, volume 9134 of Lecture Notes in Computer Science, pages 129–142. Springer, 2015. doi:10.1007/978-3-662-47672-7_11.

[bib.bib6] [6] A. Björner and G. Kalai. An extended Euler–Poincaré theorem. Acta Math., 161:279–303, 1988.

[bib.bib7] [7] J. Cibulka, M. Korbelář, J. Kynčl, V. Mészáros, R. Stolař, and P. Valtr. On three measures of non-convexity. Israel J. Math., 218:331–369, 2017.

[bib.bib8] [8] H. Edelsbrunner and J. Pach. Maximum Betti numbers of Čech complexes. In SoCG 2024, volume 293 of LIPIcs, pages 53:1–53:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.SOCG.2024.53.

[bib.bib9] [9] G. O. H. Katona. On a problem of L. Fejes Tóth. Stud. Sci. Math. Hung., 12(1–2):77–80, 1977.

[bib.bib10] [10] Chaya Keller and Micha A. Perles. Complements of finite unions of convex sets, arxiv:2508.19413, 2025. arXiv:2508.19413.

[bib.bib11] [11] M. D. Kovalev. A property of convex sets and its application. Mat. Zametki (in Russian), 44:89–99, 1988.

[bib.bib12] [12] J. Lawrence and W. D. Morris Jr. Finite sets as complements of finite unions of convex sets. Discret. Comput. Geom., 42(2):206–218, 2009. doi:10.1007/S00454-009-9184-0.

[bib.bib13] [13] J. Matoušek and P. Valtr. On visibility and covering by convex sets. Israel J. Math., 113(3):341–379, 1999.

Complements of Finite Unions of Convex Sets

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Isolated points in 𝑺.

Definition 1.

Theorem 2.

Theorem 3.

Proposition 4.

Covering 𝑺 by flats.

Definition 5.

Theorem 6.

Definition 7.

Theorem 8.

Theorem 9.

2 Bounding the number of points encapsulated by convex sets

2.1 Preliminaries

Definition 10.

Observation 11.

2.2 The number of points encapsulated by 3 convex sets in ℝ𝒅

Proof of Theorem 2.

Observation 12.

Observation 13.

Case 1: 𝐝𝐢𝐦(𝑱)=𝒅−𝟐.

Case 2: 𝐝𝐢𝐦(𝑱)<𝒅−𝟐.

Case 3: 𝐝𝐢𝐦(𝑱)=𝒅−𝟏.

Claim 14.

Proof of Claim 14.

Corollary 15.

2.3 The number of points encapsulated by 𝒏 convex sets in ℝ𝒅

Theorem 3 (Restatement).

Proof.

3 Covering the complement of finite unions of convex sets by flats

3.1 Preliminaries

Ordinary points and ordinary flats.

Definition 16.

▶ Remark 17.

Strong covers.

Definition 18.

3.2 Proof of Theorem 6

Theorem 6 (Restatement).

Proof of Theorem 6.

▶ Remark 19.

Case 1:

Case 2:

Case 2a: Any neighborhood 𝑼 of 𝒑 includes a 𝒌-simplex that is not included in 𝑯.

Case 2b: There exists a neighborhood 𝑼 of 𝒑 such that every 𝒌-simplex in 𝑺∩𝑼 is contained in 𝑯.

4 Bounding the number of ordinary hyperplanes

Theorem 20.

Theorem 21.

Proof.

Step 1.

Step 2.

Step 3.

Step 4.

Step 5.

5 The complement of the union of two convex sets

Claim 22.

Claim 23.

References

Isolated points in $𝑺$ .

Covering $𝑺$ by flats.

2.2 The number of points encapsulated by 3 convex sets in $\mathbb{R}^{d}$

Case 1: $\dim(J)=d-2$ .

Case 2: $\dim(J)<d-2$ .

Case 3: $\dim(J)=d-1$ .

2.3 The number of points encapsulated by $𝒏$ convex sets in $\mathbb{R}^{d}$

$\blacktriangleright$ Remark 17.

$\blacktriangleright$ Remark 19.

Case 2a: Any neighborhood $𝑼$ of $𝒑$ includes a $𝒌$ -simplex that is not included in $𝑯$ .

Case 2b: There exists a neighborhood $𝑼$ of $𝒑$ such that every $𝒌$ -simplex in $S\cap U$ is contained in $𝑯$ .