Document Open Access Logo

On Testing and Robust Characterizations of Convexity

Authors Eric Blais, Abhinav Bommireddi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.18.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Eric Blais
  • University of Waterloo, Canada
Abhinav Bommireddi
  • University of Waterloo, Canada

Acknowledgements

The authors thank Lap Chi Lau for numerous insightful discussions during the course of this research. The authors also thank the anonymous referees for valuable feedback and suggestions.

Cite AsGet BibTex

Eric Blais and Abhinav Bommireddi. On Testing and Robust Characterizations of Convexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.18

Abstract

A body K ⊂ ℝⁿ is convex if and only if the line segment between any two points in K is completely contained within K or, equivalently, if and only if the convex hull of a set of points in K is contained within K. We show that neither of those characterizations of convexity are robust: there are bodies in ℝⁿ that are far from convex - in the sense that the volume of the symmetric difference between the set K and any convex set C is a constant fraction of the volume of K - for which a line segment between two randomly chosen points x,y ∈ K or the convex hull of a random set X of points in K is completely contained within K except with exponentially small probability. These results show that any algorithms for testing convexity based on the natural line segment and convex hull tests have exponential query complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Convexity
  • Line segment test
  • Convex hull test
  • Intersecting cones

Metrics

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

References

  1. Keith Ball. An elementary introduction to modern convex geometry. In Flavors of geometry, chapter 1, pages 1-58. MSRI Publications, 1997. Google Scholar
  2. Imre Bárány and Zoltán Füredi. Computing the volume is difficult. Discrete & Computational Geometry, 2(4):319-326, 1987. URL: https://doi.org/10.1007/BF02187886.
  3. Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi. Testing convexity of functions over finite domains. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2030-2045. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.125.
  4. Omri Ben-Eliezer. Testing local properties of arrays. In 10th Innovations in Theoretical Computer Science Conference, ITCS, pages 11:1-11:20, 2019. Google Scholar
  5. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. The power and limitations of uniform samples in testing properties of figures. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, pages 45:1-45:14, 2016. Google Scholar
  6. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing convexity of figures under the uniform distribution. In 32nd International Symposium on Computational Geometry, SoCG, pages 17:1-17:15, 2016. Google Scholar
  7. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Tolerant testers of image properties. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55 of LIPIcs, pages 90:1-90:14, 2016. Google Scholar
  8. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In Symposium on Theory of Computing, STOC, pages 164-173, 2014. Google Scholar
  9. Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In Proceedings of the 29th Conference on Computational Complexity (CCC), pages 309-320, 2014. Google Scholar
  10. Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun. Sample-based high-dimensional convexity testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 37:1-37:20, 2017. Google Scholar
  11. Ronen Eldan. A polynomial number of random points does not determine the volume of a convex body. Discret. Comput. Geom., 46(1):29-47, 2011. Google Scholar
  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: https://doi.org/10.1145/285055.285060.
  13. Navin Goyal and Luis Rademacher. Learning convex bodies is hard. In Proceedings of the 22nd Conference on Learning Theory (COLT), 2009. Google Scholar
  14. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. Google Scholar
  15. Peter M. Gruber and Jörg M. Wills, editors. Handbook of Convex Geometry. North-Holland, 1993. Google Scholar
  16. Jiří Matoušek. Lectures on discrete geometry, volume 108. Springer, 2002. Google Scholar
  17. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM J. Comput., 32(5):1158-1184, 2003. Google Scholar
  18. Luis Rademacher and Santosh Vempala. Testing geometric convexity. In Proceedings of the 24th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 469-480, 2004. Google Scholar
  19. Sofya Raskhodnikova. Approximate testing of visual properties. In 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM, volume 2764 of Lecture Notes in Computer Science, pages 370-381. Springer, 2003. Google Scholar
  20. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: https://doi.org/10.1137/S0097539793255151.
  21. Santosh Vempala. Recent progress and open problems in algorithmic convex geometry. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 42-64, 2010. Google Scholar
  22. Grigory Yaroslavtsev. Open problems in L_p-testing. Problem 70 on sublinear.info, 2016. URL: https://sublinear.info/70.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact