Let $K_0$ be a bounded convex set in $\mathbf{R}^n$ within which lie two sets $K_1$ and $K_2$. Assume that,
- $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
- The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, we assume that the boundary is not a hyperplane.)
- Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.
- 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$).