Testing Convexity of Figures Under the Uniform Distribution

Authors Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.17.pdf
  • Filesize: 1.98 MB
  • 15 pages

Document Identifiers

Author Details

Piotr Berman
Meiram Murzabulatov
Sofya Raskhodnikova

Cite AsGet BibTex

Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing Convexity of Figures Under the Uniform Distribution. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.17

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.
Keywords
  • Convex sets
  • 2D geometry
  • randomized algorithms
  • property testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Inf. Process. Lett., 9(5):216-219, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90072-3.
  2. Imre Barany. Extremal problems for convex lattice polytopes: a survey. Contemporary Mathematics, 2000. Google Scholar
  3. Imre Bárány and Zoltán Füredi. On the shape of the convex hull of random points. Probability theory and related fields, 77(2):231-240, 1988. Google Scholar
  4. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. The role of adaptivity in image testing. Manuscript, 2015. Google Scholar
  5. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In STOC, pages 164-173, 2014. URL: http://dx.doi.org/10.1145/2591796.2591887.
  6. Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, 2014, pages 309-320, 2014. Google Scholar
  7. Bernard Chazelle and C. Seshadhri. Online geometric reconstruction. J. ACM, 58(4):14, 2011. URL: http://dx.doi.org/10.1145/1989727.1989728.
  8. Artur Czumaj and Christian Sohler. Property testing with geometric queries. In Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings, pages 266-277, 2001. URL: http://dx.doi.org/10.1007/3-540-44676-1_22.
  9. Artur Czumaj, Christian Sohler, and Martin Ziegler. Property testing in computational geometry. In Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings, pages 155-166, 2000. URL: http://dx.doi.org/10.1007/3-540-45253-2_15.
  10. Herbert Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer, 1987. URL: http://dx.doi.org/10.1007/978-3-642-61568-9.
  11. Ronen Eldan. A polynomial number of random points does not determine the volume of a convex body. Discrete and Computational Geometry, 46(1):29-47, 2011. URL: http://dx.doi.org/10.1007/s00454-011-9328-x.
  12. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: http://dx.doi.org/10.1145/285055.285060.
  13. Sariel Har-Peled. On the expected complexity of random convex hulls. CoRR, abs/1111.5340, 2011. URL: http://arxiv.org/abs/1111.5340.
  14. Igor Kleiner, Daniel Keren, Ilan Newman, and Oren Ben-Zwi. Applying property testing to an image partitioning problem. IEEE Trans. Pattern Anal. Mach. Intell., 33(2):256-265, 2011. URL: http://dx.doi.org/10.1109/TPAMI.2010.165.
  15. Simon Korman, Daniel Reichman, and Gilad Tsur. Tight approximation of image matching. CoRR, abs/1111.1713, 2011. Google Scholar
  16. Simon Korman, Daniel Reichman, Gilad Tsur, and Shai Avidan. Fast-match: Fast affine template matching. In CVPR, pages 2331-2338, 2013. URL: http://dx.doi.org/10.1109/CVPR.2013.302.
  17. Nimrod Megiddo. Partitioning with two lines in the plane. J. Algorithms, 6(3):430-433, 1985. URL: http://dx.doi.org/10.1016/0196-6774(85)90011-2.
  18. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM J. Comput., 32(5):1158-1184, 2003. URL: http://epubs.siam.org/sam-bin/dbq/article/41402.
  19. Luis Rademacher and Santosh Vempala. Testing geometric convexity. In FSTTCS, pages 469-480, 2004. Google Scholar
  20. Sofya Raskhodnikova. Approximate testing of visual properties. In RANDOM-APPROX, pages 370-381, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45198-3_31.
  21. Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM J. Comput., 39(3):813-842, 2009. Google Scholar
  22. Sofya Raskhodnikova and Grigory Yaroslavtsev. Learning pseudo-Boolean k-DNF and submodular functions. In SODA, pages 1356-1368, 2013. Google Scholar
  23. H Raynaud. Sur l'enveloppe convexe des nuages de points aleatoires dans r n. i. Journal of Applied Probability, 7(1):35-48, 1970. Google Scholar
  24. Alfréd Rényi and Rolf Sulanke. Über die konvexe hülle von n zufällig gewählten punkten. Probability Theory and Related Fields, 2(1):75-84, 1963. Google Scholar
  25. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
  26. Bernd Schmeltz. Learning convex sets under uniform distribution. In Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, pages 204-213, 1992. Google Scholar
  27. C. Seshadhri and Jan Vondrák. Is submodularity testable? Algorithmica, 69(1):1-25, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9719-2.
  28. Wojciech Szpankowski. Average Case Analysis of Algorithms on Sequences. John Wiley &Sons, Inc., New York, 2001. Google Scholar
  29. Gilad Tsur and Dana Ron. Testing properties of sparse images. In FOCS, pages 468-477, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.52.
  30. John W Tukey. Mathematics and the picturing of data. In Proceedings of the international congress of mathematicians, volume 2, pages 523-531, 1975. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail