# When does the finite union of convex sets have a hole in it?

Let $f_1, \dots, f_j$ be convex functions from $\mathbb{R}^n \to \mathbb{R}$. I am trying to develop a test that decides whether or not the set $\{x | f_1(x) \le k_1\} \cup \dots \cup \{x | f_n(x) \le k_n\}$ has a hole in it of any size (the alternative is that the set is homeomorphic to the unit ball, maybe plus a few lower-dimensional "fingers").

Editing in some extra information that is specific to my particular use for this algorithm. In my algorithm, $n$ of the convex sets that I'm unioning together are the coordinate planes (i.e. $\{x | x_j = 0\}$), and there are exactly $n$ additional convex sets that I care about (so $j = 2n$).

-
So it is actually a union and not an intersection? – Gerald Edgar Apr 27 '13 at 0:46
1. You're really asking about the union (not intersection :-) of closed convex sets. 2. Are you attempting a practical algorithm? Then you need restrictions on your convex sets. Algorithms must depend on restrictions (while there is none that would work well universally). – Włodzimierz Holsztyński Apr 27 '13 at 1:00
1. Yes, it's the union, not the intersection of the sets (the intersection would be convex =) ). 2. Yes, I am attempting a floating-point algorithm. Rather than place restrictions on the sets, I'm hoping to use standard convex optimization techniques as a subroutine (the $\epsilon$-fudginess in these techniques is okay; I'd be fine with an algorithm that reports "the functions come within $\epsilon$ of being hole-less"). – user21816 Apr 27 '13 at 1:09
If you have a way test whether intersections of the convex sets are nonempty, you can adapt the solution to this problem: mathoverflow.net/questions/21911/… – zeb Apr 27 '13 at 1:56
Man, that is a cool answer you linked to. I do have a way to test intersections, so that will do perfectly. – user21816 Apr 27 '13 at 2:49

Let $K=K_1\cup\dots\cup K_n$ and $K_i$ are convex.
Consider the nerve $N$ of your covering $K_i$. Note that $N$ is homotopically equivalent to $K$. (To find $N$ you only need an algorithm which decides that given subcollection of $K_i$ has nonempty intersection.)
Calculate the homology groups of $N$ and you may get a "no" answer if you are (un)lucky.