Computer Science/Discrete Mathematics Seminar I | |

Topic: | An Application of the Universality Theorem for Tverberg Partitions |

Speaker: | Imre Barany |

Affiliation: | Renyi Institute, Hungary and UCL, London |

Date: | Monday, March 18 |

Time/Room: | 11:00am - 12:00pm/Simonyi Hall 101 |

Video Link: | https://video.ias.edu/csdm/2019/0318-ImreBarany |

We show that, as a consequence of a remarkable new result of Attila P\'or on universal Tverberg partitions, any large-enough set $P$ of points in $\Re^d$ has a $(d+2)$-sized subset whose Radon point has half-space depth at least $c_d \cdot |P|$, where $c_d \in (0, 1)$ depends only on $d$. We then give an application of this result to computing weak $\eps$-nets by random sampling. Joint work with Nabil Mustafa.