## Complexity of detecting a convex body in $\mathbb{R}^n$?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. 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, I 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 $\mathbf{x},\mathbf{y}$ on hand, where $\mathbf{x}\in K_1$ and $\mathbf{y}\in K_2$.

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

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

My questions:

1. Can this be done with finite number of queries?
2. What is the complexity class of this problem?

Thanks.

-
Can this be done? Consider for example $K_0$ is a disk; $K_1$ is some point on the boundary (or maybe a tiny arc), and $K_2$ is the rest. It seems that with high probability, a method based on queries will declare $K_2$ to be convex, and miss out on $K_1$. Or am I mistaken? – S. Sra Nov 6 2011 at 21:32
@Suvrit: there is no doubt that more information is needed for any sort of efficiency, but all the OP is asking for is AN algorithm. – Igor Rivin Nov 6 2011 at 21:42
It's clear that there can't be a query-based algorithm whose worst-case complexity is bounded: for any algorithm and any $n$ you can construct examples where the boundary is so close to a hyperplane that more than $n$ queries will be needed. So I don't know what Han means by "as few membership queries as possible". – Robert Israel Nov 6 2011 at 22:49
On the other hand, here's an algorithm that will eventually work if the interior of one of the sets is non-convex: take a sequence of points $x_n$ dense in $K_0$, and for each pair $i < j$ such that $x_i$ and $x_j$ are both in $K_1$ or both in $K_2$, check whether $(x_i + x_j)/2$ is there too. – Robert Israel Nov 6 2011 at 22:50
Actually that algorithm requires that the convex set has nonempty interior. – Robert Israel Nov 7 2011 at 1:52
show 1 more comment

You haven't said precisely what you mean by an algorithm here, and this is actually a nontrivial issue since your question is outside the usual finitary context of computability theory, so it isn't clear what you might mean, and there are choices to be made about it.

One way to make the concept precise would be to work with $\mathbb{Q}^n$ rather than $\mathbb{R}^n$ (or some other countable dense set), that is, to finitize the problem by regarding all the relevant reals as rational. In this case, we can use a standard Turing machine concept of computability to make the question precise. For this manner of formalization, we regard the "input" as fixing the oracles for the $K_i$, and the question is whether there is a Turing machine program that can detect the answer correctly regardless of the oracle (subject to them satisfying your hypotheses). Let me assume first that the hypotheses are that exactly one of the $K_i$ are non-convex.

Theorem. With the $\mathbb{Q}^n$ formalization just described, the answer is yes, there is an algorithm.

Proof. Consider the algorithm that systematically produces all triples $(p,q,r)$ of rational points in $\mathbb{Q}^n$, such that $q$ is on the line from $p$ to $r$, and checks membership in each $K_i$. Note that any instance of non-convexity will therefore be revealed. Thus, we will at some finite time in the algorithm, discover which of the $K_i$ is not convex, and thus produce the correct answer in finitely many steps. QED

The previous algorithm relied on the fact that instances of non-convexity can be discovered in finitely many steps.

Theorem. In the $\mathbb{Q}^n$ formalization, in the context where the input sets $K_1$ and $K_2$ might both be convex (and in such a case only, we allow the boundary to be a hyperplane), then there is no computable procedure that will always work.

Proof. Suppose that there were such a procedure in the case $n=1$. Let $K_0=(0,2)$, $K_1=(0,1)$ and $K_2=[1,2)$. The algorithm will halt in finitely many steps, having made queries about reals $q_0$, $q_1$, ... $q_n$, and stating that one of the sets, lets suppose $K_1$, is convex, which is true. Consider now the modification of the sets by letting $r$ be the largest $q_i$ below $2$ (or $\frac32$, whichever is larger), and using $K_1'=(0,1)\cup (r,2)$ and $K_2'=[1,r]$. Since the answers to the queries about the $q_i$ are exactly the same for this configuration as in the original problem, the algorithm will again say that $K_1'$ is convex, but in this case, it would be incorrect. QED

Since the $K_i$ input is infinitary in nature, it isn't immediately clear what you might mean by "complexity class". However, the problem does have an inherent semi-decidable nature, since instances of non-convexity are revealed by a single instance. In the case where one side or the other must be non-convex, this semi-decidable nature becomes decidable, since we can know which is convex by discovering the other set to be non-convex.

Let us now try to consider the general case of $\mathbb{R}^n$. We don't have a standard formal notion of computability here (there are several distinct notions of computability on the reals, such as BSS machines, computable analysis, descriptive set-theoretic notions of "computability", infinite time computability). Note that the input to the algorithm is the sets $K_i$, rather than a real number.

But let's try to be flexible and allow a more generous concept of algorithm, subject to the following properties: an algorithm is a deterministic procedure that (somehow) produces points $p$ in $\mathbb{R}^n$, makes inquiries about whether they are in $K_0$, $K_1$ and $K_2$, and then uses the resulting yes/no answers to those queries to produce additional real numbers about which queries may be made. Eventually, based on the result of the queries, the algorithm is supposed to give an output by specifying whether $K_1$ or $K_2$ is convex. In particular, in this set-up, the same algorithm can be used with many different $K_0$, $K_1$ and $K_2$, and the reals produced depend only on the answers to the queries, rather than on the oracle sets themselves. We give the "input" of $K_i$ to the algorithm by attaching the black boxes, without providing any additional information about the $K_i$ sets, except that they satisfy the assumptions you identified. In this case, it doesn't matter whether one insist that exactly one or at most one $K_i$ is non-convex.

Theorem. With the $\mathbb{R}^n$ manner of formalization just described, there can be no algorithm correctly identifying a convex $K_i$.

Proof. Suppose that there were such an algorithm in the case $n=1$. Call the algorithm $e$. Consider the set $Q$ of all real numbers that will ever be produced by the algorithm $e$ for a membership query for any combination of sets $K_0$, $K_1$ and $K_2$. Our assumptions on the nature of the algorithm ensure that $Q$ is a countable set, since any real produced during the course of any computation is produced as the result of a finite sequence of yes/no answers to the previous queries, and there are only countably many such possible patterns of membership. Let $r\lt s\lt t$ be real numbers not in $Q$, and consider the two possible inquiries:

• $K_0=[r,t]$, $K_1=\{r\}\cup[s,t]$, $K_2=(r,s)$.
• $K_0=[r,t]$, $K_1=[s,t)$, $K_2=[r,s)\cup\{t\}$.

Because these two input configurations agree on $Q$, the algorithm must give the same output for both of them. But in the first case, it $K_2$ that is convex, while in the second, it is $K_1$ that is convex. So there can be no such algorithm. QED

-
Just a remark to show the distinction between $\mathbb{Q}^n$ and $\mathbb{R}^n$ can be significant: There are nonrational polytopes, ones for which there are no combinatorially equivalent polytopes with rational coordinates. In particular, Perles constructed a 12-vertex 8-dimensional nonrational polytope. – Joseph O'Rourke Nov 7 2011 at 18:01
Interesting! In the application of my argument, however, one could replace $\mathbb{Q}$ with the algebraic reals or any countable dense set of reals that can be finitely represented, and this may avoid such obstacles. – Joel David Hamkins Nov 7 2011 at 18:03
Sorry for being dense (no puns intended), could you rephrase formally what it means to be a convex set in terms of purely $\mathbb{Q}$? – S. Sra Nov 7 2011 at 21:25
I meant $K\subset\mathbb{Q}^n$ is convex, if whenever $x,y\in K$ and $z\in\mathbb{Q}^n$ is on the line joining $x$ to $y$, then $z\in K$. Thus, violations of convexity are semi-decidable, in the sense that one can know by means of a specific example that a set is not convex. – Joel David Hamkins Nov 8 2011 at 13:28
@Joel David Hamkins Thanks for your very detailed answer. Indeed, my problem formulation on $\mathbb{R}^n$ is problematic and imprecise. Thanks for pointing it out. I'm glad to see your first two theorems are established by restricting $\mathbb{R}^n$ to a countable dense set, which is what I meant. – han Nov 8 2011 at 13:36

Without more constraints on the problem, there is no deterministic algorithm that can decide which is convex with a finite number of queries. For randomized algorithms, I think that you can never get a finite expected number of queries.

Take $K_0$ to be a sphere. Run your algorithm, and let every query response be $K_1$. Now, whatever the response of the algorithm, we can construct a contradicting example with the same responses.

If the response was $K_1$ is convex, take $K_2$ to be a small sphere in $K_0$ that is disjoint from the query set. Then, $K_2$ is convex and $K_1$ is not.

If the response was $K_2$ is convex, we are going to take a slightly flattened sphere to be $K_1$ and the non-convex spherical cap to be $K_2$. Take the convex hull of the query points and choose a supporting hyperplane of any face of the convex hull. If we remove the spherical cap defined by the intersection of $K_0$ and the hyperplane and bulge the resulting flat face outwards, we get $K_1$ as convex and $K_2$ is not convex.

-
Your proof doesn't quite work, since the algorithm that always says points are in $K_1$ might actually never halt. You cannot guarrantee that it does halt, since the hypotheses on the sets required that $K_2$ has nonempty interior, and perhaps the algorithm only starts doing something interesting once it has found lots of points in both $K_1$ and $K_2$. – Joel David Hamkins Nov 7 2011 at 18:15
That is, what you need to do is start from an actual legal instance, let the algorithm halt with its answer, and then produce a modified version answering the queries in the same way, but having a different answer. (And this is how I argue in my answer.) – Joel David Hamkins Nov 7 2011 at 18:24
But it seems that you can do this also. Instead of letting $K_1$ always say yes, just let it do so for points on the left side of the sphere, and otherwise $K_0$ on the right side. Now you get your query points, and then shrink to the convex hull on one side or the other, so as to change the answer. – Joel David Hamkins Nov 7 2011 at 18:27
I don't understand why that objection is a problem. I've shown that for any finite number of queries, there exists a $K_2$ with nonempty interior for which none of the query points reports $K_2$. If the algorithm needs to find points in $K_2$ to do something interesting, I can keep playing hide-and-seek with $K_2$, for any finite number of queries. So, either the algorithm halts and gives an incorrect answer, or it doesn't halt in a finite number of steps. – Michael Biro Nov 7 2011 at 18:34
The point is that it isn't a problem for it not to halt in a finite number of steps in that instance, since it wasn't a legitimate input. I've realized that the left/right solution I've proposed also doesn't fix the issue, since in the left/right division, the boundary is a plane, which isn't allowed. So again there is no guarantee that the main algorithm will halt in that case, and so we never get the finite list of queries. – Joel David Hamkins Nov 7 2011 at 18:37
show 1 more comment