文章基本信息

标题：On Testing and Robust Characterizations of Convexity
本地全文：下载
作者：Eric Blais ; Abhinav Bommireddi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：18:1-18:15
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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