An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets

Abstract We show that, as a consequence of a new result of Por on universal Tverberg partitions, any large-enough set P of points in R d has a ( d + 2 ) -sized subset whose Radon point has half-space depth at least c d ⋅ | P | , where c d ∈ ( 0 , 1 ) depends only on d. We then give two applications of this result. The first is to computing weak ϵ-nets by random sampling. The second is to show that given any set P of points in R d and a parameter ϵ > 0 , there exists a set of O ( ϵ − ⌊ d 2 ⌋ + 1 ) ⌊ d 2 ⌋ -dimensional simplices (ignoring polylogarithmic factors) spanned by points of P such that they form a transversal for all convex objects containing at least ϵ ⋅ | P | points of P.