MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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").

Is anything known about this problem?

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$).

share|cite|improve this question
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:… – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.