National Center for Supercomputing Applications master calendar

View Full Calendar

NCSA staff who would like to submit an item for the calendar can email

Eliot Robson "No-dimensional Tverberg Partitions Revisited"

Event Type
Illinois Computer Science
3401 Siebel Center for Computer Science
Oct 9, 2023   10:00 am  
Eliot Robson (UIUC)
Candice Steidinger
Originating Calendar
Computer Science Speakers Calendar

We look forward to seeing you in-person today in 3401 Siebel Center for Computer Science. 

Abstract: Given a set P⊂Rd of n points, with diameter Δ, and a parameter δ∈(0,1), it is known that there is a partition of P into sets P1,…,Pt, each of size O(1/δ^2), such that their convex-hulls all intersect a common ball of radius δΔ. 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 ε-net theorem with an improved constant. 

Joint work with Sariel Har-Peled. .

link for robots only