摘要：A body K âS, â"â¿ 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.
关键词：Convexity; Line segment test; Convex hull test; Intersecting cones
