Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 26, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Daniel Bertschinger
Given any point set P ⊆ ℝd consisting of n points, a weighted ε-net is defined as a set of points p1,…,pk and some values ε = (ε1,…,εk) such that every set in the range space containing more than εin points of P contains at least i of the points p1,…,pk. It is a notion of approximation for point sets in ℝd similar to ε-nets and ε-approximations, where it is stronger than the former and weaker than the latter. We analyze small weak weighted ε-nets with respect to convex sets and show that for any point set of size n in ℝd and for any positive α ≤ β with (i) dα + β ≥ d and (ii) α ≥ (2d-1)/(2d+1) we can find two points p1 and p2 such that each convex set containing more than αn points of P contains at least one of p1 and p2 and each convex set containing more than βn points contains both p1 and p2. For axis-parallel boxes in ℝd instead of convex sets we can improve the conditions.
Automatic MiSe System Software Version 1.4803M | admin login