| Abstract: | We consider the following basic geometric problem: Given  , a 2‐dimensional black‐and‐white figure is ?‐ far from convex if it differs in at least an ? fraction of the area from every figure where the black object is convex. How many uniform and independent samples from a figure that is ?‐ far from convex are needed to detect a violation of convexity with constant probability? This question arises in the context of designing property testers for convexity. We show that  uniform samples (and the same running time) are necessary and sufficient for detecting a violation of convexity in an ?‐far figure and, equivalently, for testing convexity of figures with 1‐sided error. Our algorithm beats the  lower bound by Schmeltz 32] on the number of samples required for learning convex figures under the uniform distribution. It demonstrates that, with uniform samples, we can check if a set is approximately convex much faster than we can find an approximate representation of a convex set. |
