### Presentation 1 - ETH - D-INFK

```Lower bounds for epsilon-nets
Gabriel Nivasch
Presenting work by: Noga Alon,
János Pach, Gábor Tardos
Epsilon-nets
Let R be a family of ranges. Say, R = {all discs in R2}.
Let P be a finite point set.
Let 0 < ε < 1 b a parameter.
A subset N of P is an ε-net w.r.t. R if, for
every r in R that contains at least ε|P|
points of P, r contains a point of N.
Want N as small as possible.
P
Epsilon-nets
Let R be a family of ranges. Say, R = {all discs in R2}.
Let P be a finite point set.
Let 0 < ε < 1 b a parameter.
A subset N of P is an ε-net w.r.t. R if, for
every r in R that contains at least ε|P|
points of P, r contains a point of N.
Want N as small as possible.
P
N
ε|P| = 4
Epsilon-nets
Let R be a family of ranges. Say, R = {all discs in R2}.
Let P be a finite point set.
P
Let 0 < ε < 1 b a parameter.
N
A subset N of P is an ε-net w.r.t. R if, for
every r in R that contains at least ε|P|
points of P, r contains a point of N.
Want N as small as possible.
ε|P| = 4
[Haussler, Welzl, ‘87]: If R has finite
VC-dimension then there exists N of
size O(1/ε log 1/ε). Indep. of |P|.
Examples of families of ranges:
R = {all rectangles in R2}
R = {all ellipsoids in Rd}
R = {all convex sets in R2}
R = {all halfspaces in Rd}
Infinite
VC-dim
Epsilon-nets
General belief until recently: In geometric settings, there always
exist ε-nets of size O(1/ε).
But:
• [Bukh, Matoušek, N. ‘09]: Ω(1/ε logd–1 1/ε) for
weak ε-nets w.r.t. convex sets in Rd.
• [Alon ‘10]: Ω(1/ε α(1/ε)) for ε-nets w.r.t. lines in R2. (*)
• [Pach, Tardos ‘11]:
• Ω(1/ε log log 1/ε) for ε-nets w.r.t. axis-parallel
rectangles in R2. (Tight [Aronov, Ezra, Sharir ‘10].)
• Ω(1/ε log 1/ε) for dual ε-nets for axis parallel
rectanlges in R2.
• Ω(1/ε log 1/ε) for ε-nets w.r.t. axis-parallel
boxes and w.r.t. halfspaces in R4.
Lower bound for axis-parallel
rectangles
[Pach, Tardos ‘11]: Ω(1/ε log log 1/ε) for ε-nets w.r.t.
axis-parallel rectangles in R2.
Proof strategy: Given n, we will construct an n-point set
P such that every ε-net N for P has size > n/2.
For ε suitably chosen in terms of n.
(Spoiler: ε = (log log n) / n.)
Lower bound for axis-parallel
rectangles
[Pach, Tardos ‘11]: Ω(1/ε log log 1/ε) for ε-nets w.r.t.
axis-parallel rectangles in R2.
Proof strategy: Given n, we will construct an n-point set
P such that every ε-net N for P has size > n/2.
???
It should say
“Given ε”
For ε suitably chosen in terms of n.
(Spoiler: ε = (log log n) / n.)
???
Normally |N|
does not depend
on |P|
Lower bound for axis-parallel
rectangles
[Pach, Tardos ‘11]: Ω(1/ε log log 1/ε) for ε-nets w.r.t.
axis-parallel rectangles in R2.
Proof strategy: Given n, we will construct an n-point set
P such that every ε-net N for P has size > n/2.
???
It should say
“Given ε”
For ε suitably chosen in terms of n.
(Spoiler: ε = (log log n) / n.)
We’ll fix both problems later on.
???
Normally |N|
does not depend
on |P|
Lower bound for axis-parallel
rectangles
Given n, we will construct an n-point set P such that every ε-net N
for P has size > n/2 (for ε suitably chosen).
Construction: P is a set of n random points in the unit square.
We will show: With high probability, every subset N of n/2 points
misses some heavy axis-parallel rectangle.
Rectangle that contains εn points.
Lower bound for axis-parallel
rectangles
Choosing n random points in the unit square:
• Step 0: Choose the y-coordinates, and place all points at the left side.
• Step 1: Jump right by 1/2?
• Step 2: Jump right by 1/4?
…
• Step t: Jump right by 2–t?
…
Lower bound for axis-parallel
rectangles
Let N be a subset of n/2 points of P.
We will calculate the probability that N misses some heavy rectangle.
We will look at steps t = 1, 2, …, tmax, where tmax = log2 1/(2ε).
N
Lower bound for axis-parallel
rectangles
Let N be a subset of n/2 points of P.
We will calculate the probability that N misses some heavy rectangle.
We will look at steps t = 1, 2, …, tmax, where tmax = log2 1/(2ε).
N
Just before step t, the points lie on
2t–1 vertical lines:
…
2t–1
Lower bound for axis-parallel
rectangles
For each vertical line, partition the points into intervals, where each
interval contains exactly εn black points.
“orphans”
Lower bound for axis-parallel
rectangles
For each vertical line, partition the points into intervals, where each
interval contains exactly εn black points.
“orphans”
We want a rectangle to be heavy, and
to be missed by N:
2–t
At step t:
• none of the black points should jump,
• all the red points should jump.
Lower bound for axis-parallel
rectangles
For each vertical line, partition the points into intervals, where each
interval contains exactly εn black points.
“orphans”
Claim 1: There are at most n/4
black orphans (by choice of tmax).
Proof:
# black orphans ≤ 2t–1*εn ≤ 1/(4ε)*εn = n/4.
tmax = log2 1/(2ε)
Claim 2: There are at least 1/(4ε) intervals.
Proof: # intervals ≥ (n/4) / (εn) = 1/(4ε).
Lower bound for axis-parallel
rectangles
Call an interval good if it contains at most 3εn red points; otherwise
Claim: There are at least 1/(12ε) good intervals.
Proof:
total # intervals ≥ 1/(4ε)
# bad intervals ≤ (n/2) / (3εn) = 1/(6ε)
# good intervals ≥ 1/(4ε) – 1/(6ε) = 1/(12ε)
Lower bound for axis-parallel
rectangles
Focus on good rectangles – rectangles of good intervals:
At most 4εn points
Pr[ given good rectangle is heavy and missed by N ] ≥ 2–4εn
# good rectangles in first tmax stages ≥ 1/(12ε) tmax ≈ 1/ε log 1/ε
tmax = log2 1/(2ε)
Pr[ our N is a good ε-net ] ≤ (1 – 2–4εn )1/ε log 1/ε ≤ e–1/ε log 1/ε * 2^(–4εn)
1 – x ≤ e–x
Lower bound for axis-parallel
rectangles
Pr[ our N is a good ε-net ] ≤ e–1/ε log 1/ε * 2^(–4εn)
# subsets N of size n/2 ≤ 2n
Pr[ some N is a good ε-net ] ≤ 2n – 1/ε log 1/ε * 2^(–4εn)
union bound
Want to choose ε in terms of n so that this probability tends to 0.
Let ε = (log log n) / (8n). Get:
2n – n / (log log n) * (log n) * 1/√(log n) = 2n – n (√ log n)/ (log log n)  0
Lower bound for axis-parallel
rectangles
To summarize, an ε-net N for P must have size at least n/2,
for ε = (log log n) / n.
Express |N| in terms of ε: |N| ≥ Ω(1/ε log log 1/ε)
Finally:
Theorem: For every ε there exists an n0 s.t. for every n ≥ n0
there exists an n-point set P that requires ε-nets w.r.t. axisparallel rectangles of size Ω(1/ε log log 1/ε).
Proof: To get larger sets P, replace every point by a tiny
cloud of points.
Lower bound for lines
Theorem [Alon ‘10]: For every ε there exists an n0 and
there exists an n0-point set P that requires ε-nets w.r.t.
lines of size Ω(1/ε α(1/ε)).
Note: No arbitrarily large n. “Cloud” method does not work,
because lines are infinitely thin.
Proof uses the density Hales-Jewett theorem, which is about
playing high-dimensional tic-tac-toe:
Density Hales-Jewett theorem
Density Hales-Jewett Theorem [Furstenberg, Katznelson ‘91]:
For every integer k and every real δ > 0 there exists an m such
that, no matter how you select a δ fraction of the points of a
k*k*k*…*k
m
tic-tac-toe board, you will contain a complete line of size k
(maybe diagonal).
[Polymath ‘09]: Elementary proof that gives a bound on m:
It is enough to take m ≈ Ak(1/δ).
Lower bound for lines
Back to ε-nets w.r.t. lines in the plane:
• Let δ = 1/2 (density).
• Given k (board side), let m be the dimension guaranteed by DHJ.
So m ≈ Ak(constant) ≈ A(k).
• Project the board into R2 in “general position” (so that no point
falls into a line it does not belong to).
3*3*3
Lower bound for lines
Number of points: n = km ≈ kA(k) ≈ A(k)
Choose ε so that εn = k, namely ε = k/n.
Then, every ε-net w.r.t. lines N must have more than n/2 points,
since otherwise, the missing points would be more than a δ
fraction, so a whole line would be completely missed.
|N| ≥ n/2 = k/(2ε) ≈ 1/ε α(1/ε)
1/ε = n/k ≈ A(k) / k ≈ A(k)  k ≈ α(1/ε)
|N| = Ω(1/ε α(1/ε))
QED
```