Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, September 26, 2019, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Daniel Bertschinger

Weighted ε-Nets

Given any point set P ⊆ ℝ^d consisting of n points, a weighted ε-net is defined as a set of points p₁,…,p_k and some values ε = (ε₁,…,ε_k) such that every set in the range space containing more than ε_in points of P contains at least i of the points p₁,…,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₁ and p₂ such that each convex set containing more than αn points of P contains at least one of p₁ and p₂ and each convex set containing more than βn points contains both p₁ and p₂. 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:   2025  2024  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