A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1 2). Recent exciting work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. In fact, the Lovett-Meka algorithm finds a half integral point in any "large enough" polytope. However, their algorithm crucially relies on the facet structure and does not apply to general convex sets. We show that for any symmetric convex set K with measure at least exp(-n 500), the following algorithm finds a point y in K [-1,1]^n with Omega(n) coordinates in -1,+1 : (1) take a random Gaussian vector x; (2) compute the point y in K [-1,1]^n that is closest to x. (3) return y. This provides another truly constructive proof of Spencer's theorem and the first constructive proof of a Theorem of Gluskin and Giannopoulos.
More generally, the theorem of Banaszczyk @cite_11 shows that for any convex set @math with Gaussian measure at least @math and any set of vectors @math of length @math , there exist signs @math so that @math .
@cite_11
1496278954
In this paper we present several results on the expected complexity of a convex hull of @math points chosen uniformly and independently from a convex shape. (i) We show that the expected number of vertices of the convex hull of @math points, chosen uniformly and independently from a disk is @math , and @math for the case a convex polygon with @math sides. Those results are well known (see rs-udkhv-63,r-slcdn-70,ps-cgi-85 ), but we believe that the elementary proof given here are simpler and more intuitive. (ii) Let @math be a set of directions in the plane, we define a generalized notion of convexity induced by @math , which extends both rectilinear convexity and standard convexity. We prove that the expected complexity of the @math -convex hull of a set of @math points, chosen uniformly and independently from a disk, is @math , where @math is the largest angle between two consecutive vectors in @math . This result extends the known bounds for the cases of rectilinear and standard convexity. (iii) Let @math be an axis parallel hypercube in @math . We prove that the expected number of points on the boundary of the quadrant hull of a set @math of @math points, chosen uniformly and independently from @math is @math . Quadrant hull of a set of points is an extension of rectilinear convexity to higher dimensions. In particular, this number is larger than the number of maxima in @math , and is also larger than the number of points of @math that are vertices of the convex hull of @math . Those bounds are known bkst-anmsv-78 , but we believe the new proof is simpler.