Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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). –  Wlodzimierz Holsztynski 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
add comment

1 Answer

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|improve this answer
add comment

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.