Efficient method for detecting a convex body in $\mathbb{R}^n$

Question

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

Answer 1

Given the constraints, I think the following approach will be close to optimal.

Start by randomly querying points until you have 1 point in one set and 2 in the other. You then have the endpoints of two segments crossing the boundary.

By using bisection on each of those segments, you can find pairs of points in either set arbitrarily close to the boundary. If one of the sets, say $K_1$, is strictly convex, ultimately you will find two points in $K_2$ close enough to the boundary that their mean is in $K_1$. This then shows that $K_2$ is not convex.

Answer 2

Let $K_0$ be the unit disk in $\mathbb{R}^2$. $K_1$ consists of the point at $(1,0)$ and some other point $\zeta$ uniformly and randomly chosen on the boundary of $K_0$ (the unit circle). It is not convex. $K_2$ is the complement of $K_1$ in $K_0$. It is convex. Therefore this is a valid instance of the problem.

Suppose you start with $x$ at $(1,0)$ any $y$ in $K_2$, say at $(0,0)$. The probability that any given algorithm ever queries $\zeta$ is $0$. Therefore, almost surely, the result of all queries will be to detect additional points in $K_2$, but never any additional points in $K_1$. One will therefore be unable to determine which of $K_1$ or $K_2$ is the convex subset.

Contemplate a similar situation in which $K_1$ is the intersection of a ball of radius $\delta$ around $(1,0)$ with $K_0$ and again $x$ is at $(1,0)$. This time, $K_1$ is convex and $K_2$ is not. Given any algorithm that purports to solve the problem and any natural number $N$, choose $\delta$ so small that the algorithm does not probe $K_1$ within $N$ steps. (If it is a stochastic algorithm, the tiny diameter of $K_1$ implies the chance of probing it will be vanishingly small). This shows the number of steps in the algorithm is unbounded (or the expected number of steps is arbitrarily large if the algorithm is stochastic). The best we can say is that the two sets can be differentiated using a number of steps proportional to a ratio of the areas.

To distinguish among the two cases, you are essentially undertaking a search for a second point in $K_1$ (which is tiny), but all your probes are always returning points in $K_2$. Evidently a completely random search (uniformly over $K_0$) is going to perform as well as anything else might. (Once you obtain $2$ points within each of $K_1$ and $K_2$, the game is almost over: it's straightforward to construct a small number of additional points that tell you which is the convex subset.)

These considerations don't rule out a solution to the problem, but they imply either that the solution must depend on additional assumed properties of $K_1$ and $K_2$; e.g., that they both have positive measure with a known nonzero lower bound, or else that a different model of space is needed; e.g., that it is totally discrete and contains a finite number of points (which is a more realistic model of what computers usually do).