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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Mittagsseminar Talk Information

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 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.

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