דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
נתן רובין (אונ' בן-גוריון)
event date icon
יום רביעי, 01.06.2022, 12:30
event location icon
טאוב 201
Given a finite point set $P$ in $R^d$, and $\eps>0$ we say that a point set $N$ in $R^d$ is a weak $\eps$-net if it pierces every convex set $K$ with $|K\cap P|\geq \eps |P|$. Let $d\geq 3$. We show that for any finite point set in $R^d$, and any $\eps>0$, there exists a weak $\eps$-net of cardinality $o(1/\eps^{d-1/2})$. Here $delta>0$ is an arbitrary small constant. This is the first improvement of the bound of $O^*(1/\eps^d)$ that was obtained in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for general point sets in dimension $d\geq 3$. The study of weak epsilon-nets is closely related to the fundamental problem of finding a point that hits many simplices in a dense $(d+1)$-uniform geometric hypergraph.