No-dimensional Tverberg Partitions Revisited

newcommandepsAMhδ newcommandReℝ newcommandrealsℝ newcommandSetXmathsfX renewcommandPP newcommanddiamDelta newcommandMh[1]#1 newcommandqueryq newcommandepsvarepsilon newcommandVorX[1]V pth#1 newcommandIntRange[1][ #1 ] newcommandSpaceoverlinemathsfm newcommandpth[2][!]#1left(#2right) newcommandpolylogpolylog newcommandNmathbb N newcommandZmathbb Z newcommandptp newcommanddistY[2]left| #1 - #2 right| newcommandPPP newcommandptqq newcommandptssGiven a set P subset Red of n points, with diameter diam, and a parameter epsA ∈ (0,1), it is known that there is a partition of P into sets P1, ldots, Pt, each of size O(1/epsA2), such that their convex-hulls all intersect a common ball of radius epsA diam. We prove that a random partition, with a simple alteration step, yields the desired partition, resulting in a (randomized) linear time algorithm. We also provide a deterministic algorithm with running time O( dn log n). Previous proofs were either existential (i.e., at least exponential time), or required much bigger sets. In addition, the algorithm and its proof of correctness are significantly simpler than previous work, and the constants are slightly better. We also include a number of applications and extensions using the same central ideas. For example, we provide a linear time algorithm for computing a ``fuzzy'' centerpoint, and prove a no-dimensional weak eps-net theorem with an improved constant.