Personal tools
You are here: Home CG seminar 2022 Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions
« December 2021 »
December
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
262728293031
Log in


Forgot your password?
 

Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions

Wednesday, December 15th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

underline

Natan Rubin, Ben Gurion University

Abstract:

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})$,

where \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$.

Document Actions