2026-07-25T13:19:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12621 2024-03-06T10:51:16Z ddc:004 open_access

On Testing and Robust Characterizations of Convexity Blais, Eric Bommireddi, Abhinav Convexity Line segment test Convex hull test Intersecting cones 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Blais and Abhinav Bommireddi 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.18 urn:nbn:de:0030-drops-126214 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.18 eng https://creativecommons.org/licenses/by/3.0/legalcode