Testing Geometric Convexity

Abstract. We consider the problem of determining whether a given set S in R n is approximately convex, i.e., if there is a convex set K ∈ R n such that the volume of their symmetric difference is at most ǫ vol(S) for some given ǫ. When the set is presented only by a membership oracle and a random oracle, we show that the problem can be solved with high probability using poly(n)(c/ǫ) n oracle calls and computation time. We complement this result with an exponential lower bound for the natural algorithm that tests convexity along “random ” lines. We conjecture that a simple 2-dimensional version of this algorithm has polynomial complexity.