An interesting 2D conjecture...

Prahladh Harsha and Jaikumar Radhakrishnan post a summary (on the Complexity blog) of this year's FSTTCS at Chennai, India. One of the papers they mention is Testing geometric convexity by Rademacher and Vempala.

The paper discusses (in the property-testing framework) the problem of checking if a given shape S is convex. The natural approximate formulation of this problem is: is there a convex shape C such that the symmetric difference of S and C has volume at most an ε-fraction of vol(S) ? Of course, one needs a way of asking queries like "is x in S ? ". They use this membership oracle and a random oracle that returns a (uniform) random point of S to show that

• In 1D, the problem can be solved efficiently in time 1/ε
• In Rⁿ, the problem can be solved in time exponential in n and polynomial in 1/ε

An interesting conjecture emerges from all of this. The fact that the problem is solvable in 1D suggests the use of line queries: pick two random points x, y and test whether the intersection of the line joining them and S is convex. They show that in general one might need an exponential number of such line queries (which in itself is interesting) and conjecture that using two-dimensional sectional queries might work instead.