Stronger bounds for weak epsilon-nets in higher dimensions
Natan Rubin (Ben-Gurion University)
Abstract: Given a finite point set $P$ in $R^d$, and $\varepsilon>0$ we say that a point set $N$ in $R^d$ is a weak $\varepsilon$-net if it pierces every convex set $K$ with $|K\cap P|\geq \varepsilon |P|$. Let $d\geq 3$. We show that for any finite point set in $R^d$, and any $\varepsilon>0$, there exists a weak $\varepsilon$-net of cardinality $O(1/\varepsilon^{d-1/2+\delta})$, where $\delta>0$ is an arbitrary small constant.
This is the first improvement of the bound of $O^*(1/\varepsilon^d)$ that was obtained in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for general point sets in dimension $d\geq 3$.
computational geometrydiscrete mathematicscommutative algebracombinatorics
Audience: researchers in the topic
Copenhagen-Jerusalem Combinatorics Seminar
Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.
The password for the zoom room is 123456
Organizers: | Karim Adiprasito, Arina Voorhaar* |
*contact for this listing |