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

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

-
Do you know anything at all about $K_1$ and $K_2$ apart from the fact that one of them is convex? –  tards Nov 4 '11 at 15:44
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. –  han Nov 4 '11 at 15:50
$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). –  Florian Nov 4 '11 at 16:57
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. –  han Nov 4 '11 at 17:50
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$. –  Christian Blatter Nov 5 '11 at 11:57

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

-

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.

-
Thanks, but suppose one of these two bodies is a convex polytope, which means the boundary between $K_1$ and $K_2$ is a set of hyperplanes $\mathcal{H}=\{H_1,H_2,\ldots,H_n\}$. I think this approach will fail when two points are on the same hyperplane $H\in \mathcal{H}$. –  han Nov 5 '11 at 9:12
@han: That's why I said <em>strictly</em> convex. If neither set is strictly convex the problem becomes much harder, because the evidence needed may be hidden in some small corner. On the other hand, in many cases this method will still produce a result with a fairly high probability. –  Niels Diepeveen Nov 5 '11 at 23:33
Thanks @NielsDiepeveen for the remark. It is true that this algorithm can make a correct decision with high probability after testing enough pairs. I'm trying to figure out how high is that. –  han Nov 6 '11 at 7:43