10
$\begingroup$

Let $K_0$ be a bounded convex set in $\mathbf{R}^n$ within which lie two sets $K_1$ and $K_2$. Assume that,

  1. $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
  2. The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, we assume that the boundary is not a hyperplane.)
  3. Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.
  4. We have two initial points $x,y$ on hand, where $x\in K_1$ and $y\in K_2$. (Please see the update below.)

Essentially, $K_0$ can be viewed as a black box. Further assume that one can query any point in $K$ with a membership oracle, namely a procedure that given a point $x\in K$, reports the set contains $x$.

The goal is to determine which set is convex using as few membership queries as possible.

Is there an algorithm for doing this?


Update:

To make sampling in $K_1$ and $K_2$ (also $K_0$) feasible, I further assume we have two initial points $x$ and $y$, where $x\in K_1$ and $y\in K_2$. Therefore, one can employ for instance hit-and-run algorithm with starting point $x$ (or $y$) to sample points in $K_1$ (or $K_2$).

  • 0
    Do you know anything at all about $K_1$ and $K_2$ apart from the fact that one of them is convex?2011-11-04
  • 0
    Besides three assumptions listed above, I don't know any other information about $K_1$ and $K_2$. The only information can be used is the _membership oracle_, which reports whether a query point $x$ is in $K_1$ or in $K_2$, but provides no other information.2011-11-04
  • 0
    $K_1 \cap K_2=\emptyset$, so the distance between these two is strictly positive, thus it is not possible that $K_1 \cup K_2=K_0$ is convex (except in the trivial case that one of $K_1,K_2$ is empty).2011-11-04
  • 0
    Assume $K_0$ is a hypercube in $\mathbf{R}^n$. $K_1$ is a hypersphere in this cube and $K_2=K_1^c$. It satisfies the first assumption and $K_0$ is convex.2011-11-04
  • 0
    You cannot have "two compact bodies $K_1$ and $K_2$" and at the same time the conditions 1 as stated. You will have to specify what exactly happens along the boundary between $K_1$ and $K_2$.2011-11-05
  • 0
    Thanks Christian Blatter, point taken.2011-11-05
  • 0
    Assume $K_0$ is the cube $[{-1},1]^n$, and $K_1$ is the half cube $x_1\leq0$ minus a tiny simplex at the corner $(0,1, 1,\ldots,1)$. Such an algorithm would have to hit a point in that simplex before it would come to a decision.2011-11-05
  • 0
    Thanks @ChristianBlatter for the remark. It's true that a trivial sampler will take a long time to mix on such $K_1$. Fortunately, there is an [algorithm](http://dl.acm.org/citation.cfm?id=1146015&CFID=52311479&CFTOKEN=63186434) for bringing a convex body into near-isotropic position.2011-11-05

2 Answers 2