Berman, Piotr ;
Murzabulatov, Meiram ;
Raskhodnikova, Sofya
Testing Convexity of Figures Under the Uniform Distribution
Abstract
We consider the following basic geometric problem: Given epsilon in (0,1/2), a 2dimensional figure that consists of a black object and a white background is epsilonfar from convex if it differs in at least an epsilon fraction of the area from every figure where the black object is convex. How many uniform and independent samples from a figure that is epsilonfar 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 (1sided 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 epsilonfar from convex.
We show that Theta(epsilon^{4/3}) uniform samples are necessary and sufficient for detecting a violation of convexity in an epsilonfar figure and, equivalently, for testing convexity of figures with 1sided error. Our testing algorithm runs in time O(epsilon^{4/3}) and thus beats the Omega(epsilon^{3/2}) sample lower bound for learning convex figures under the uniform distribution from the work of Schmeltz (Data Structures and Efficient Algorithms,1992). 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.
BibTeX  Entry
@InProceedings{berman_et_al:LIPIcs:2016:5909,
author = {Piotr Berman and Meiram Murzabulatov and Sofya Raskhodnikova},
title = {{Testing Convexity of Figures Under the Uniform Distribution}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {17:117:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5909},
URN = {urn:nbn:de:0030drops59094},
doi = {10.4230/LIPIcs.SoCG.2016.17},
annote = {Keywords: Convex sets, 2D geometry, randomized algorithms, property testing}
}
2016
Keywords: 

Convex sets, 2D geometry, randomized algorithms, property testing 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 