Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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 p_{1},…,p_{k} and some values ε = (ε_{1},…,ε_{k}) such that every set in the range space containing more than ε_{i}n points of P contains at least i of the points p_{1},…,p_{k}. 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 p_{1} and p_{2} such that each convex set containing more than αn points of P contains at least one of p_{1} and p_{2} and each convex set containing more than βn points contains both p_{1} and p_{2}. For axis-parallel boxes in ℝ^{d} instead of convex sets we can improve the conditions.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login