Combinatorics Seminar - Natan Rubin

16:15-18:00

Speaker: Natan Rubin

Title: Stronger bounds for weak epsilon-nets in higher dimensions

Abstract: Given a finite point set $\mathrm{P }$in $R^d$, and $\epsilon >\mathrm{0 }$we say that a point set $\mathrm{N }$in $R^{\mathrm{d }}$is a weak $\mathrm{<br>}$-net if it pierces every convex set $K$ with $\mathrm{\mid }K\cap P\mathrm{\mid }\ge \epsilon \mathrm{\mid }P\mathrm{\mid }$. Let $d\ge 3$. We show that for any finite point set in $R^d$, and any $\epsilon >0$, there exists a weak $\mathrm{<br>}$-net of cardinality $O(1\mathrm{/}{\epsilon }^{d-1\mathrm{/}2+\delta })$, where $\delta >\mathrm{0 }$is an arbitrary small constant.

This is the first improvement of the bound of $O^{\ast }(1\mathrm{/}{\epsilon }^d)$that was obtained in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for general point sets in dimension $d\ge 3$.