1
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ So it is actually a union and not an intersection? $\endgroup$
    – Gerald Edgar
    Commented Apr 27, 2013 at 0:46
  • $\begingroup$ 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). $\endgroup$
    – Włodzimierz Holsztyński
    Commented Apr 27, 2013 at 1:00
  • $\begingroup$ 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"). $\endgroup$
    – user21816
    Commented Apr 27, 2013 at 1:09
  • 2
    $\begingroup$ 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/… $\endgroup$
    – zeb
    Commented Apr 27, 2013 at 1:56
  • $\begingroup$ Man, that is a cool answer you linked to. I do have a way to test intersections, so that will do perfectly. $\endgroup$
    – user21816
    Commented Apr 27, 2013 at 2:49

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .