TY - GEN

T1 - Testing convexity of figures under the uniform distribution

AU - Berman, Piotr

AU - Murzabulatov, Meiram

AU - Raskhodnikova, Sofya

N1 - Funding Information:
The second author was supported by NSF CAREER award CCF-0845701. The third author was supported by NSF award CCF-1422975 and NSF CAREER award CCF-0845701.
Publisher Copyright:
© Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova.

PY - 2016/6/1

Y1 - 2016/6/1

N2 - We consider the following basic geometric problem: Given ε ∈ (0, 1/2), a 2-dimensional figure that consists of a black object and a white background 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 probability at least 2/3? This question arises in the context of designing property testers for convexity. Specifically, a (1-sided error) tester for convexity gets samples from the figure, labeled by their color; it always accepts if the black object is convex; it rejects with probability at least 2/3 if the figure is ε-far from convex. We show that Θ(ε-4/3) uniform samples 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 testing algorithm runs in time O(ε-4/3) and thus beats the Ω(ε-3/2) sample lower bound for learning convex figures under the uniform distribution from [26]. It shows 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.

AB - We consider the following basic geometric problem: Given ε ∈ (0, 1/2), a 2-dimensional figure that consists of a black object and a white background 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 probability at least 2/3? This question arises in the context of designing property testers for convexity. Specifically, a (1-sided error) tester for convexity gets samples from the figure, labeled by their color; it always accepts if the black object is convex; it rejects with probability at least 2/3 if the figure is ε-far from convex. We show that Θ(ε-4/3) uniform samples 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 testing algorithm runs in time O(ε-4/3) and thus beats the Ω(ε-3/2) sample lower bound for learning convex figures under the uniform distribution from [26]. It shows 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.

UR - http://www.scopus.com/inward/record.url?scp=84976897437&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976897437&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2016.17

DO - 10.4230/LIPIcs.SoCG.2016.17

M3 - Conference contribution

AN - SCOPUS:84976897437

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 17.1-17.15

BT - 32nd International Symposium on Computational Geometry, SoCG 2016

A2 - Fekete, Sandor

A2 - Lubiw, Anna

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 32nd International Symposium on Computational Geometry, SoCG 2016

Y2 - 14 June 2016 through 17 June 2016

ER -