## 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: Tuesday, September 11, 2012, 11:30 am

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Gábor Tardos (Alfréd Rényi Institute of Mathematics)

## Tight lower bounds for geometric epsilon nets

Assume we are given a set $S$ of $n$ points in the plane and want find a subset $T$ of these points with the property that every half-plane containing at least $\epsilon n$ points of $S$ contains at least one point of $T$. Such a set $T$ is called an $\epsilon$-net for $S$ with respect to half-planes. The well known theorem of Haussler and Welzl states that an $\epsilon$-net of size $O((1/\epsilon)\log(1/\epsilon))$ exists for any set $S$ and not just with respect to half-planes but also with respect to any any bounded VC-dimension collection of ranges. (All reasonable collections such as triangles, pentagons, disks, etc. have bounded VC dimension.)

While the Haussler-Welzl theorem is very general in many specific geometric settings such as the half-planes or even half-spaces in 3D a stronger statement is also true: $O(1/\epsilon)$ size $\epsilon$-nets exist (Matousek, Seidel, Welzl). In other cases intermediate results were shown: Ezra and Sharir showed recently that for axis-aligned rectangles in the plane or axis-aligned boxes in 3D $O((1/\epsilon)\log\log(1/\epsilon))$ size $\epsilon$-nets exist. Based on these and similar results a "general belief" was formed that the Haussler-Welzl bound is never tight in geometric settings and in "reasonable" cases a linear (that is $O(1/\epsilon)$) bound holds.

Contrary to this belief we construct point sets $S$ in the 4 dimensional Euclidean space such that all $\epsilon$-nets with respect to either half-spaces or axis-aligned boxes have size $\Omega((1/\epsilon)\log(1/\epsilon))$ showing that the Haussler-Welzl bound is tight in this case. In another construction we find planar point sets showing that the Ezra-Sharir bound on $\epsilon$-nets with respect to axis-aligned rectangles is also tight.

Information for students and suggested topics for student talks