License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.17
URN: urn:nbn:de:0030-drops-59094
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5909/
Go to the corresponding LIPIcs Volume Portal

Berman, Piotr ; Murzabulatov, Meiram ; Raskhodnikova, Sofya

Testing Convexity of Figures Under the Uniform Distribution

pdf-format:
LIPIcs-SoCG-2016-17.pdf (2 MB)

Abstract

We consider the following basic geometric problem: Given epsilon in (0,1/2), a 2-dimensional figure that consists of a black object and a white background is epsilon-far 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 epsilon-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 epsilon-far from convex.

We show that Theta(epsilon^{-4/3}) uniform samples are necessary and sufficient for detecting a violation of convexity in an epsilon-far figure and, equivalently, for testing convexity of figures with 1-sided 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:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5909},
  URN =		{urn:nbn:de:0030-drops-59094},
  doi =		{10.4230/LIPIcs.SoCG.2016.17},
  annote =	{Keywords: Convex sets, 2D geometry, randomized algorithms, property testing}
}

Keywords: Convex sets, 2D geometry, randomized algorithms, property testing
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI