Lecture Notes

Combinatorics in the Plane

Torsten Ueckerdt
March 12, 2015

1
Contents
1 The Sylvester-Gallai Theorem 3

2 The Crossing Lemma 10

2.1 Applications of the Crossing Lemma . . . . . . . . . . . . . . . . 15

3 The Sliding Game 24

3.1 The Geometric Sliding Game . . . . . . . . . . . . . . . . . . . . 25

4 Convexity 29
4.1 Sets of Constant Width . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 Centerpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Ham Sandwiches . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Convex Independent Subsets . . . . . . . . . . . . . . . . . . . . 50
4.5 Empty Convex Independent Subsets . . . . . . . . . . . . . . . . 56

5 Coloring Problems 62
5.1 Coloring Points with respect to Ranges . . . . . . . . . . . . . . . 65
5.2 The Dual Coloring Problem . . . . . . . . . . . . . . . . . . . . . 73
5.3 Online Coloring Problems . . . . . . . . . . . . . . . . . . . . . . 79
5.4 Semi-Online Coloring Problems . . . . . . . . . . . . . . . . . . . 89

2
1 The Sylvester-Gallai Theorem
Every finite set of points in the plane naturally defines a set of lines – the
connecting lines. A connecting line is a line passing through at least two points
of the set. Some of the oldest as well as some of the hardest problems in
combinatorial geometry ask to find point sets whose set of connecting lines are
extreme in some sense.
Maybe the most famous example is the following question posed by James
Joseph Sylvester (1814-1897) in 1893.
“Is it true that any finite set of points in the plane, not all on a line, has two
elements whose connecting line does not pass through a third point?”
After several failed attempts the problem was rediscovered by Erdős 40 years
later. Shortly thereafter, an affirmative answer was given by Tibor Grünwald
(alias Gallai) [Gal44]. We present here the “book proof” found by Kelly.
Theorem 1.1 (Sylvester-Gallai theorem).
For any finite non-collinear set of points in the plane there is a line passing
through exactly two of them.
Proof. Consider a pair (p, `) of a point p in our set and a line ` passing through
at least two points with p not on `, for which the distance between p and ` is
minimal. We claim that ` passes through exactly two points.
Suppose not, i.e., that ` contains at least three points. Then there is a ray
that is contained in `, emerges from the projection of p onto ` and contains at
least two points from our set, say q and r. Assume without loss of generality that
r is closer to p than q is. Then the distance between r and the line connecting
p and q is smaller than the distance between p and `. This contradicts the
minimality of the pair (p, `) and completes the proof.

r
q
p

Figure 1: Illustrating the proof of the Sylvester-Gallai theorem.

For a given finite point set P a line that goes through exactly two points from
P is called an ordinary line. A natural question in combinatorial geometry is to
find the minimum number ol(n) of ordinary lines determined by n non-collinear
points in the plane. The Sylvester-Gallai theorem asserts that ol(n) ≥ 1 for all
n ≥ 3. Despite the time it took to prove this bound, people believe that the
true value is much bigger.
Conjecture 1.1 (Dirac [Dir51], Motzkin).
For every n 6= 7, 13, we have
n
ol(n) ≥ d e.
2

3
 Kelly and Moser [KM58] proved ol(n) ≥ 73 n, with equality for n = 7 (see
6
Figure 2(a)). The best known lower bound is ol(n) ≥ 13 n, with equality for
n = 13 (see Figure 2(b)), was proven by Csima and Sawyer [CS93, CS95].

(a) (b)

Figure 2: Exceptional sets with n = 7 and n = 13 points and fewer than d n2 e

ordinary lines (drawn dotted). It is conjectured that such examples do not exist
for n 6= 7, 13.

Next we prove an upper bound on ol(n), i.e., find finite point sets defining
very few ordinary lines. It is convenient to define these point sets in the real
projective plane, which we define here as the projective completion of R2 .
Definition 1.1 (Real projective plane).
Consider R2 and add for each parallel class of lines one new point, called a
point at infinity. Each point at infinity lies on every line of the corresponding
parallel class and no further line from R2 . Moreover, all points at infinity lie
on a common new line, called the line at infinity, and no point from R2 lies on
this line.

The real projective plane is denoted by RP2 and has the following beautiful
properties.

• Every two distinct points lie on a unique line.

• Every two distinct lines meet in a unique point.

The first property is also satisfied by the real plane R2 . However, by the
second property there are no parallel lines in RP2 , which clearly exist in R2 .
In the upcoming constructions proving Theorem 1.3 we identify certain parallel
classes of lines and let the corresponding points at infinity be in our constructed
set. The same is already done in Figure 2(b). However, every finite sets of
points and lines in RP2 can transformed into one in R2 with the same point-line
incidences. For the examples in Figure 2 and Figure 3 this can be achieved by
applying some small perturbations to the points. We remark that this can be
done in general but omit the proof and a detailed explanation.

4
Theorem 1.2. Every finite set S of points and lines in the real projective plane
is in bijection with a finite set S 0 of points and lines in the real plane such that
each of the following holds.

• A point and a line in S are incident if and only if their images in S 0 are
incident.
• Two lines in S are concurrent if and only if their images in S 0 are con-
current.

• Three points in S are collinear if and only if their images in S 0 are

collinear.
In particular there are no parallel lines in S 0 .
An easy case analysis shows ol(3) = 3, ol(4) = 3, and ol(5) = 4. In Theo-
rem 1.3 below we assume n ≥ 6.
n
Theorem 1.3. For even n we have ol(n) ≤ 2. For odd n we have ol(n) ≤ 3b n4 c.

Proof. For even n, consider a regular n2 -gon Q in RP2 , which determines n2

directions. Let P be the set of corners of Q together with the n2 projective
points corresponding to the directions determined by Q. See Figure 3(a) for
an example. Then for each corner of Q there is exactly one direction for which
the corresponding line goes through no other corner of Q. Hence the number of
ordinary lines is exactly n2 .

(a) (b) (c)

Figure 3: (a) A set of n = 8 points defining only n2 = 4 ordinary lines. (b) A set
of n = 9 points defining only 3b n4 c = 6 ordinary lines. (c) A set of n = 7 points
defining only 3b n4 c = 3 ordinary lines. All ordinary lines are drawn dotted.

If n ≡ 1 (mod 4), we take the above construction on n − 1 points and add

the center of the polygon Q to the set. See Figure 3(b) for an example. From
n ≡ 1 (mod 4) follows that Q has an even number of corners and hence all n−1 4
diagonals of Q meet in a common point, the center. Thus the ordinary lines
are given as the union of the n−1
2 ordinary lines from the construction on n − 1
points plus another n−1
4 ordinary lines each containing the center and one point
at infinity.
Finally, if n ≡ 3 (mod 4), we take the construction on n + 1 points and
remove one of the points at infinity from it. See Figure 3(c) for an example.
Again from n ≡ 3 (mod 4) follows that Q has an even number of corners and

5
hence the ordinary lines in the example with n+1 points use only n+1
4 directions.
We delete the point at infinity for such a direction. This way two ordinary lines
contain now only one point and are no longer ordinary, while n−1 2 lines of that
direction are now ordinary as the number of points on them drops from three
to two.
Remark. On March 28, 2013 (less than three weeks ago!) Ben Green and Ter-
ence Tao [GT13] claimed to have proven the Dirac-Motzkin conjecture (Conjec-
ture 1.1) for large n. Their proof also seems to give a lower bound of 3b n4 c in
case of odd n.

Problem 1.
Show that given any set of n non-collinear points in the plane determines
at least n different connecting lines, i.e., lines through at least two points
of the set.
Show moreover that n points define exactly n connecting lines if and
only if all but one of the points are collinear.

Let us continue with the Sylvester-Gallai theorem in its dual version. One
of the most pleasing aspects of considering the real projective plane RP2 rather
than the real Euclidean plane R2 is that RP2 comes with a very natural concept
of duality between points and lines. Note that the two properties of RP2 below
Definition 1.1 can be transformed into one-another by swapping the meaning of
points and lines.
Theorem 1.4 (Duality in real projective plane).
For every configuration S of points and lines in RP2 we can find a dual config-
uration S ∗ in RP2 with the following properties.
• Every point in S corresponds to one line in S ∗ and vice versa.
• Every line in S corresponds to one point in S ∗ and vice versa.
• A point and a line in S are incident if and only if the corresponding line
and point in S ∗ are incident.
• A set of points in S is collinear if and only if the corresponding lines in
S ∗ are concurrent.
• A set of lines in S is concurrent if and only if the corresponding points in
S ∗ are collinear.

See Figure 4 for an example of a configuration and one of its dual config-
urations. We remark that configurations are considered here as actual points
and lines in the real projective plane. This makes the dual configuration not
unique. Indeed, applying any “small” perturbation to one dual configuration
yields another, different dual configuration. For example, the configuration in
the right of Figure 4 can be modified so that the lines C and D are parallel and
1 is the point at infinity where these two lines meet.

6
 4 5
2
3
A D B 5 3
B 4 1
2
C A
1 C
D

Figure 4: A configuration S in RP2 (left) and a dual configuration S ∗ of S

(right).

Problem 2.
Find a dual configuration of the configuration with 7 points and 9 lines in
Figure 2(a).

Figure 5: An arrangement of 13 lines in the real projective plane (the 13the line
is the line at infinity) determining only 6 ordinary points: The 4 gray points
and the 2 points where the bold lines intersect the line at infinity.

With Theorem 1.4 and Theorem 1.2 we can formulate the Sylvester-Gallai
theorem (Theorem 1.1) in its dual form. Instead of finite point sets in R2
defining ordinary lines we now speak of arrangements of lines defining ordinary
points, i.e., points contained in exactly two lines.
Theorem 1.5 (Sylvester-Gallai theorem – dual version).
Every arrangement of finitely many lines in R2 , not all concurrent, and not all
parallel, admits an ordinary point.
Although the dual Sylvester-Gallai theorem is equivalent to its primal ver-
sion, we give an alternative proof for it, which indeed is a little stronger. For a
given arrangement A of lines in RP2 we define the vertices, edges and faces of
A to be the points where two lines intersect, the connected components of lines
after the removal of all vertices, and the connected components of RP2 after the
removal of all lines, respectively.

7
 Note that in the projective plane, every line contains as many vertices as
edges. Figuratively speaking, the two “ends” of a line meet at the point at
infinity and hence belong to the same edge, unless the point at infinity is a vertex
of A. Similarly, in the figures some faces of A appear as a pair of unbounded
regions on opposite sites of the arrangement, in particular such faces look as if
they were disconnected. We refer to Figure 6 for an illustrative example.

1 2 4
3
5
6 8
7 9
11
6
10

5 12 1
4 2

Figure 6: An arrangement of lines in RP2 with 7 vertices (on being a point at

infinity), 18 edges and 12 faces.

The main ingredient for the proof of Theorem 1.5 is Euler’s formula for
arrangements of lines in the real projective plane.
Proposition 1.1 (Euler).
If A is a projective arrangement of lines with f0 vertices, f1 edges and f2 faces,
then
f0 − f1 + f2 = 1. (1)

Problem 3.
Find a proof for Proposition 1.1.

Proof of Theorem 1.5.

Let A be a fixed arrangement of lines in R2 . We interpret A as an arrangement
of lines in RP2 and thus can speak of vertices, edges and faces in A. Let si be
the number of vertices of A where exactly i lines meet, i ≥ 2. Secondly, let tj
be the number of faces of A with exactly j incident edges, j ≥ 1. With f0 , f1
and f2 denoting the number of vertices, edges and faces in A, respectively, we
have
X X
si = f0 and t j = f1 .
i≥2 j≥1
P
Because every edge is incident to two faces, we have j≥1 j · tj = 2f1 .
Because a vertex in which exactly i lines meet has 2i incidences
P with edges and
every edge has two incidences with vertices, we have i≥2 2i · si = 2f1 . Using
all these equalities we calculate

X X (1)
(3 − i)si + (3 − j)tj = 3f0 − f1 + 3f2 − 2f1 = 3(f0 − f1 + f2 ) = 3.
i≥2 j≥1

8
 Now if not all lines in A are concurrent, then there exist at least two vertices,
which implies that t1 = t2 = 0. Thus in the leftmost term above the only positive
coefficient is the one for s2 , and it is 1. We conclude s2 ≥ 3, which means that
there are at least three ordinary points.

Problem 4.
For any arrangement A of lines in R2 , i.e., in the Euclidean plane, we define
the vertices, edges and faces of A as the points where two lines intersect,
the connected components of lines after the removal of all vertices, and the
connected components of R2 after the removal of all lines, respectively.
Consider simple arrangements, that is, arrangements in which no point
in R2 belongs to more than two lines in A, with n lines. Derive and prove
a formula for the total number vertices, edges and faces of A.

9
2 The Crossing Lemma
Disclaimer: In this chapter for the first time we deal with graphs. We omit a
detailed introduction into the basic terminology, such as vertices/nodes, edges,
paths, cycles, trees, loops, parallel edges, degree of vertices, complete graphs,
bipartite graphs, and so on. Let us just remark that all graphs considered here
are finite and simple, i.e., we allow neither loops nor parallel edges.

We are interested in topological drawings of graphs. In particular, we want

to draw vertices as points and edges as continuous curves connecting the two
endpoints of the edge. We forbid edges to pass through vertices, just as we
forbid two vertices to be drawn on the same spot. For simplicity we refer to
topological drawings simply as drawings. Figure 7 shows drawings of K5 , the
complete graph on 5 vertices, K3,3 , the complete bipartite graph on 3 and 3
vertices, and two drawings of the dodecahedron graph.

(a) (b)

(c)

Figure 7: (a) A drawing of K5 . (b) A drawing of K3,3 , where the bipartition

classes are given by black and white vertices, respectively. (c) Two drawings of
the dodecahedron graph.

Certainly, the two drawings of the dodecahedron graph highlight different

aspects of the graph. In the drawing on the left no two edges intersect except in
their endpoints. Whereas the drawing on the right contains many such crossings.
Finding drawings with as few crossings as possible is a very important topic in
graph theory - and that not only for aesthetically reasons. However, as we will
see later, understanding the matter of crossing minimization has far reaching
consequences for seemingly unrelated areas, some of which we want to present
here.
Definition 2.1 (Crossing number).
A crossing is a point in the intersection of at least two edges but distinct from all

10
vertices. The crossing number of a drawing of a graph is the number of crossings


in the drawing, where a crossing that is contained in k edges is counted k2 times.
The crossing number of G, denoted by cr(G), is the least crossing number in
any drawing of G.

Problem 5.
Show that in the definition of cr(G) we can safely restrict our attention to
drawings with the following properties.
• No two incident edges cross.
• No pair of edges crosses more than once.

• No edge crosses itself.

• No three edges cross in a common point.
Would the same be true if we restrict in our drawings that all edges are
drawn as a straight segments?

Of course, the best one can hope for is crossing number 0, i.e., a drawing in
which no pair of edges cross. Such drawings are called plane drawings, or plane
embeddings, and the graphs admitting such drawings are called planar graph.
For example Figure 7(c) certifies that the dodecahedron graph is planar. We
remark that neither K5 nor K3,3 are planar. Indeed both graphs have crossing
number 1, even though Figure 7(b) only proves cr(K3,3 ) ≤ 3.
We have defined drawings, and hence the crossing number, in such a way
that edges can be drawn as arbitrary curves. Allowing this freedom obviously
strengthens most of the results below. On the other hand, restricting the draw-
ings of edges, e.g., as straight-line segments, or circular arcs, gives nice and
interesting variants.
Let us just just briefly mention the most important notions and facts. The
rectilinear crossing number of a graph G, denoted by cr(G), is the minimum
number of crossings in a drawing of G where every edge is a straight-line seg-
ment. Fáry’s Theorem [Fár48] states that for any graph G we have cr(G) = 0 if
and only if cr(G) = 0, i.e., in case of planar graphs restricting to straight edges
is no “real restriction”.
However, in general cr(G) and cr(G) can be arbitrarily far apart.

Figure 8: The graph G with 8 light edges (drawn thin) and 18 heavy edges
(drawn thick).

11
 Problem 6.
Consider the 14-vertex graph in Figure 8; call it G.
• Prove that every topological drawing of G in which all 8 light (drawn
thin in the figure) edges are drawn as straight-line segments there
exist a crossing involving a heavy edge (drawn thick). Note that
heavy edges may be drawn arbitrarily!
• For any integer c ≥ 1 consider the graph Gc , which arises from G by
introducing c − 1 copies of every heavy edge, that is, replacing each
such each by a bundle of c parallel edges, and subdividing each of
these heavy edges with a new vertex if degree two. Show that

cr(Gc ) ≤ 4 and cr(Gc ) ≥ c.

Back to topological drawings. One of the first questions coming to our mind
may be the following.
“What causes a graph to have a large crossing number?”
Intuitively, if the graph has many edges on few vertices, then there should
be many crossings in every drawing of that graph. The Crossing Lemma given
below quantifies this intuition very precisely. In particular, it gives a function
f : N × N → R such that every n-vertex m-edge graph has crossing number at
least f (m, n). Before coming to the Crossing Lemma itself, let us first prove
two weaker, yet powerful, lower bounds.
We start by counting the maximum number of edges in any n-vertex planar
graph, that is, graph with crossing number 0. It suffices to consider maximally
planar graphs only, that is, graphs with a planar drawing for which the addition
of any edge would necessarily introduce a crossing. A face in such a planar
drawing is a connected component of the plane after the removal of all vertices
and edges; The outer face being the one corresponding to the unbounded com-
ponent. It is easy to see that in a maximally planar graph on at least 3 vertices
every face is bounded by a simple (without vertex repetition) cycle of length 3
– a triangle. Hence these graphs are also called triangulated, while a graph is
called inner triangulated if it admits a planar drawing in which all inner faces
are triangles and the outer face is bounded by a simple cycle.
Proposition 2.1. Every n-vertex (n ≥ 3) inner triangulated graph has exactly
3n − 3 − k edges, where k is the length of the outer face.
Proof. Let G be an inner triangulated graph. We fix a planar drawing of G in
which all inner faces are triangles. We prove the statement by induction on the
number of vertices of G.
If n = 3, then G itself is a triangle and the outer face has length k = 3.
Hence |E(G)| = 3 = 3n − 3 − k.
So let n > 3. A chord of the outer face is an edge that is not on the outer
face but connects two vertices on the outer face. Let v be any vertex on the
outer face that is not incident to any chord. If there is no chord, we can take
any vertex from the outer face. If there exist at least one chord, consider one for

12
which the two endpoints, say u and w, have minimum distance along the outer
face, and let v be any vertex different from u and w on the shorter path P on
the outer face between u and w. Note that u and w have distance at least 2 on
the outer face and hence v is well-defined. Since the drawing is planar, every
chord starting at v would have to end on P again, which would contradict the
minimality of the chord uw. The situation is illustrated in the left of Figure 9.
u
P
G\v
v v
w

Figure 9: Illustration of the proof of Proposition 2.1.

Now consider the graph G \ v, that is the inner triangulated graph after the
removal of vertex v and all its incident edges. Since v has no incident chord all
but two neighbors of v lie in the interior of G and all neighbors of v lie on the
outer face of G \ v. See the right of Figure 9. So if d denotes the degree of v in
G, then the length of the outer face of G \ v is k + d − 3. Applying induction to
G \ v we obtain |E(G \ v)| = 3(n − 1) − 3 − (k + d − 3) and thus

|E(G)| = |E(G \ v)| + d = 3(n − 1) − 3 − (k + d − 3) + d = 3n − 3 − k.

From Proposition 2.1 immediately implies that every n-vertex planar graph
has at most 3n − 6 edges. The next is a direct generalization of this fact.
Proposition 2.2. Any drawing of an n-vertex m-edge graph has at least m −
3n + 6 crossings.
Proof. Let H be a maximal planar subgraph of our n-vertex m-edge graph G.
Then every edge in E(G)\E(H) participates in a crossing with an edge in E(H).
Since by Proposition 2.1 we have |E(H)| ≤ 3n − 6 the bound follows.
In 1973 Erdős and Guy conjectured [EG73] that every drawing of a graph
with n vertices and m edges has at least cm3 /n2 crossing for some constant c.
Two sets of authors independently confirmed this conjecture: Ajtai, Chvátal,
Newborn and Szemerédi [ACNS82] in 1982 and Leighton [Lei84] in 1984. The
statement has become very popular and is nowadays known as the Crossing
Lemma.
Theorem 2.1 (Crossing Lemma).
If G is a graph with n vertices and m ≥ 4n edges, then
1 m3
cr(G) ≥ .
64 n2
Proof. Consider a fixed drawing of G. We define a random induced subgraph
H of G by taking every vertex uniformly at random with probability p. That
H is induced means that it contains every edge of G between any two vertices
in H.

13
 Define n := |V (H)| and m := |E(H)|. Further let c be the crossing number
of the induced drawing of H. Clearly we have c ≥ cr(H) as well as the following
expectations.

E[n] = p·n (2)

2
E[m] = p ·m (3)
E[c] = p4 · cr(G) (4)

Equation (2) holds since every v ∈ V (G) is in H with probability p. An edge

uv ∈ E(G) is in H if and only if both u and v are in H. Hence the probability
that the edge uv is in H is p2 , which implies (3). For a crossing of the drawing
of G to be in the induced drawing of H, the two corresponding edges must be
in H. This is the case with probability p2 each, hence each crossing is in the
drawing of H with probability p4 , which gives (4).
With c ≥ cr(H) Proposition 2.2 gives c ≥ m − 3n independent of the actual
subgraph H. Hence this inequality holds also in expectation. Using the linearity
of expectation we can conclude

E[c] ≥ E[m − 3n]

E[c] ≥ E[m] − 3E[n]
4
p cr(G) ≥ p2 m − 3pn
m 3pn
cr(G) ≥ − 3 .
p2 p

Setting p = 4n/m (here we need the assumption m ≥ 4n) we obtain

m3 3m3 1 m3
cr(G) ≥ 2
− 2
= .
16n 64n 64 n2

The proof of the Crossing Lemma given above is attributed to Bernard

Chazelle, Micha Sharir and Emo Welzl.

Example. Consider the following drawing of a graph G = G(n, k) for positive

integers n and k with k < n/2. The vertices are (drawn as) the corners of a
convex n-gon, denoted by v0 , . . . , vn−1 in clockwise order. The edges are drawn
as straight-line segments between vertex vi and vertex vj whenever |j − i| ≤ k
(mod n). See Figure 10 for an example.
The graph G is 2k-regular, i.e., consist of n vertices and m = kn edges.
Consider any edge vi vj . This edge is crossed by every edge with one endpoint
strictly between vi and vj in clockwise order and the other endpoint strictly
between vi and vj in counterclockwise order. Thus for l = |i − j| mod n the
edge vi vj is crossed by (l − 1)2k − l(l − 1) other edges. Hence the total number
of crossings is given by
n−1
XX k
1 1 1 1 m3
(l − 1)2k − l(l − 1) = n · (2k · k 2 − k 3 + O(k 2 )) ≈ nk 3 = .
i=0 l=1
2 6 3 3 n2

14
 Figure 10: A drawing of G(n, k) with n = 16 and k = 5.

The above example shows that the Crossing Lemma is tight up to the con-
stant. The constant 1/64 ≈ 0.015 has been successively improved. The cur-
rently best lower bound is 1024/31827 > 0.032 due to Pach, Radoicic, Tar-
dos and Tóth [PRTT06]. The upper bound has been improved by Pach and
Tóth [PT97] to 0.06.
Let us recall the question we started with.

“What causes a graph to have a large crossing number?”

The Crossing Lemma (Theorem 2.1) states that if a graph has many edges
compared to its number of vertices, then it has a large crossing number. How-
ever, it is important to remark that the fraction of number of edges over number
of vertices is not the only reason for a large crossing number.

Problem 7.
Find for every c > 0 and every f > 0 a graph G = G(c, f ) with the
properties that
|E(G)|
≤ f and cr(G) ≥ c.
|V (G)|

2.1 Applications of the Crossing Lemma

As indicated earlier the Crossing Lemma is used to prove many theorems in
combinatorial geometry. (This is why it deserves to be a lemma.) We discuss
here some of the most prominent applications of the Crossing Lemma. We start
with an extremal incidence problem.

Consider a set of m points and n lines in the plane. If a point p lies on a line
`, then we say that p and ` are incident and call the pair (p, `) an incidence.
Clearly, a single point can be incident to many lines, just like a single line can
be incident to many points. On the other hand, the m points and n lines may
define no incidence at all. We start again with a very basic question.

“How many incidences can m points and n lines define at most?”

15
 Let us make this more formal. For a given finite point set P and a finite line
set L we denote by I(P, L) the set of all incidences (p, `) with p ∈ P and ` ∈ L.
For positive integers n and m we let I(n, m) be the maximum size of I(P, L)
over all n-point sets P and m-line sets L. In particular

I(n, m) := max{|I(P, L)| | |P | = n, |L| = m}.

For example, Figure 11 shows that I(3, 4) ≥ 7.

Figure 11: 3 points and 4 lines defining 7 incidences.

Problem 8.
Prove that I(3, 4) = 7 and I(5, 6) = 14.

Since I(P, L) ⊆ P ×L we get as a first upper bound I(n, m) ≤ nm. However,

this bound is far from being tight, unless n = 1 or m = 1. The following theorem
gives an upper bound on I(n, m) which is asymptotically tight. It was first
proven by Endre Szemerédi and William (aka Tom) Trotter in 1983 [STJ83].
The original proof was very involved and gave a much larger constant than the
one presented here. The proof relying on the Crossing Lemma was found by
Székely more than 10 years later [Szé97].
Theorem 2.2 (Szemerédi-Trotter).
Let I(n, m) denote the maximum number of incidences between n points and m
lines. Then
I(n, m) ≤ 4n2/3 m2/3 + 4n + m.
Proof. Let P be a set of n points and L a set of m lines. We shall show that
|I(P, L)| ≤ 4n2/3 m2/3 + 4n + m. We consider the arrangement of P and L as a
graph G. The vertices of G are the points in P , i.e., |V (G)| = |P | = n. Each
edge of G is a segment of a line ` ∈ L between two consecutive points in P . In
particular if there are k points from P on ` then there are k − 1 edges from G
contained in `. Note that without loss of generality we can assume that every
line ` ∈ L contains at least one point p ∈ P . Thus the total number of edges is
given by |E(G)| = |I(P, L)| − m. See Figure 12 for an example.
We want to apply the Crossing Lemma to G. But therefore we need |E(G)| ≥
4|V (G)|, which translates to |I(P, L)| − m ≥ 4n. In case this condition fails we
have |I(P, L)| < 4n + m, as desired. Hence we may assume that |I(P, L)| ≥
4n + m so we can apply the Crossing Lemma to G. Bounding the crossing

16
 (a) (b)

Figure 12: (a) An arrangement of a point set P and a line set L. (b) The
corresponding graph G on |P | vertices and |I(P, L)| − |L| edges.

number of the induced drawing of G very roughly by cr(G) ≤ m2 we obtain

1 (|I(P, L)| − m)3

m2 ≥ cr(G) ≥
64 n2
⇐⇒ (64m2 n2 )1/3 ≥ |I(P, L)| − m
2/3 2/3
⇐⇒ 4m n +m ≥ |I(P, L)|,

which proves the theorem.

The Szemerédi-Trotter theorem is asymptotically tight. Already in 1946
it was again Paul Erdős [Erd46] who described a set of n points and m lines
defining Ω(n2/3 m2/3 ) incidences. He also conjectured that his construction gives
the correct order of magnitude, which is confirmed by Theorem 2.2. We sketch
here the proof for m = n, as the general case is not much more difficult.
Example. Let n = 4k 3 for some natural number k. We define

P := {p = (px , py ) | px = 0, 1, 2, . . . , 4k 2 − 1, py = 0, 1, 2, . . . , k − 1}.

So P is nothing else but the 4k 2 × k grid. Further we define

L := {x = ay + b | a = 0, 1, 2, . . . , 2k − 1, b = 0, 1, 2, . . . , 2k 2 − 1}.

Figure 13 depicts the situation for k = 2.

1
Figure 13: A set of n = 32 points and 32 lines with at least 41/3
n4/3 = 64
incidences.

We claim that the intersection point of any line ` ∈ L and any horizontal
line with y-coordinate equal to 0, 1, 2, . . . , k − 1 is a point from P . Indeed, `
meets every horizontal in a point with integer coordinates and this point (x, y)
satisfies x = ay + b. Now from a ≤ 2k − 1 and b ≤ 2k 2 − 1 and y ≤ k − 1 follows

17
x ≤ 4k 2 − 1. Similarly, from a ≥ 0 and b ≥ 0 and y ≥ 0 follows x ≥ 0. Hence
(x, y) ∈ P .
Thus every line ` ∈ L is incident to at least (actually exactly) k points from
1
P , i.e., |I(P, L)| ≥ k|L| = k · 4k 3 = 41/3 n4/3 ≈ 0.63n4/3 .

Problem 9.
For a fixed point set P and a positive integer k we call a line in the plane
a big line if it contains at least k points from P . Let Bk (P ) denote the
number of big lines defined by P and Bk (n) the maximum Bk (P ) over all
point sets P with |P | = n. √
Prove that for every n and every k with 2 ≤ k ≤ n we have

n2
Bk (n) ≤ c
k3
for some constant c > 0.

The next application of the Crossing Lemma makes actually use of the fact
that edges are not necessarily drawn as straight-line segments. In 1946 Paul
Erdős [Erd46] studied the distribution of distances defined by n points in the
plane. He came up with the two simple questions. Here is the first one.

“How many distinct distances are defined by n points in the plane at least?”

We denote the minimum number of distinct distances defined by n points in

the plane by D(n). Erdős proved that
√ n
c1 n ≤ D(n) ≤ c2 √ (5)
log n
for some constants c1 , c2 > 0. In 1997 Székely [Szé97] used a generalized
version of the Crossing Lemma which deals with non-simple graphs (with more
than one edge between two vertices) to improve the lower bound to Ω(n4/5 ). We
do not present his proof here. The idea is similar to the proof of Theorem 2.4
below.
Anyways, the lower bound D(n) = Ω(n4/5 ) that one gets from the (general-
n
ized) Crossing Lemma falls far of Erdős’s upper bound D(n) = O( √log n
). In the
past decade the exponent 4/5 in the lower bound has been successively improved
4e
by Solymosi and Tóth [ST01] to 6/7, by Tardos [Tar03] to 5e−1 −  ≈ 0.863535
48−14e
and then by Katz and Tardos [KT04] to 55−16e ≈ 0.863636. Only recently, in
2010, Larry Guth and Nets Hawk Katz [GK10] obtained a breakthrough. Com-
bining ideas of György Elekes, Michar Sharir and others, they finally came up
with the following almost tight lower bound.
Theorem 2.3 (Guth-Katz).
Every set of n points in the plane defines at least c logn n distinct distances for
some c > 0, i.e.,
n
D(n) = Ω( ).
log n
Let us focus on the second question Erdős posed in 1946.

18
 “How often can a particular distance appear among n points in the plane?”

It is important to note that Erdős is interested in the most common distance

in the point set, and how often this distance can be present. Before addressing
this question, let us look at the least common distances first. I.e., we ask the
following.

“How often can a least common distance appear among n points in the plane?”

Let us denote by L(n) the maximum number of times a least common dis-
tance appears among n points. Clearly, if there are many distinct distances then
one of these distances must occur only a few times. Indeed we have
 
n
L(n) · D(n) ≤ . (6)
2
Thus inequality (6) together with Theorem 2.3 implies that L(n) ≤ cn log n
for some constant c > 0. In other words, there is a distance that occurs at most
cn log n times. But choosing the distance carefully we can do better.
Proposition 2.3. In every set of n points in the plane the maximum distance
occurs at most n times. In particular, we have

L(n) ≤ n.

Proof. Let P be any finite point set. We shall show that if a point in P is at
maximum distance to at least three points in P then there is another point in
P which is at maximum distance to only one point in P . Having this, we can
iteratively remove points that are at maximum distance to only one point until
every point in P is at maximum distance to exactly two points, which will prove
the statement.
So consider any point p ∈ P and assume that p is at maximum distance
dmax to at least three other points q, r, s ∈ P . Clearly, the four points p, q, r
and s lie in convex position, that is, span a quadrilateral with no reflex corner.
Indeed, otherwise two of the points q, r, s would have a distance greater than
dmax . Let q be the point opposite to p on the quadrilateral and assume that q
has maximum distance to another point t 6= p. See Figure 14 for an illustration.

r r
q q
p p

t
s s
(a) (b) (c)

Figure 14: (a) Point p is at distance dmax to q, r, s. (b) If q is at distance dmax

to some t, then r, t or s, t are at distance more than dmax . (c) A set of n points
defining n maximum distances.

Then p and q are opposite to each other in the quadrilateral spanned with
t and either r or s – say r. But this quadrilateral has two opposite side pr and

19
qt of length dmax implying that one of its diagonals (in fact it is rt) has length
strictly more than dmax . This is a contradiction to dmax being the maximum
distance between any two points in P .
It is easy to see that the upper bound L(n) ≤ n is best-possible. The point
set in Figure 14(c) shows that the maximum distance may appear n times among
n points. But indeed the exist sets of n points in which every distance appears
at least n times. To this end consider for odd n, say n = 2k + 1, a set of n points
at equal distance on a circle. See Figure 15 for an example. Then every point
has points at k distinct distances, two points for each distance. And since every
point in the set “looks the same” 1 there is k distances in total, each appearing
exactly n times.

Figure 15: 15 points at equal distance around a circle and the 15 occurrences
of a particular distance in gray.

Now let us turn to the Erdős’ original problem, namely how often can a par-
ticular distance appear among n points in the plane. Without loss of generality,
i.e., by appropriate scaling, we can fix the particular distance to be 1. We then
denote the maximum number of unit distances defined by n points in the plane
by U (n). Erdős proved that

n1+c/ log log n ≤ U (n) ≤ n3/2 (7)

for some positive constant c. He also conjectured that his lower bound on
U (n) in (7), as well as his upper bound on D(n) in (5) are asymptotically best-
possible. Remarkably, both bounds are attained by the square grid of suitable
cell size.
Of course, D(n) and U (n) are closely related by
 
n
U (n) · D(n) ≥ . (8)
2
However, inequality (8) goes in the wrong direction in order to get upper
bounds on U (n) from lower bounds√on D(n). In fact, it is the other way around.
Erdős’ upper bound
√ D(n) = O(n/ log n) in (5) implies the weaker lower bound
U (n) = Ω(n · log n). And every upper bound on U (n) of the form n1+ would
immediately imply a lower bound on D(n) of the form (1/2)n1− . But as of
today the best known upper bound on U (n) is the following application of the
Crossing Lemma.
1 We omit to introduce the formal definition of a transitive point set here.

20
Theorem 2.4. Every set of n points in the plane defines at most 8n4/3 unit
distances, i.e.,
U (n) ≤ 8n4/3 .
Proof. Let P be a set of n points in the plane defining the maximum number of
unit distances. Denoting by U (P ) the number of unit distances defined by P ,
we have to prove that U (P ) ≤ 8n4/3 .
For every point p ∈ P we draw a circle Cp centered at p and with unit radius.
The number of resulting point-circle incidences is exactly 2U (P ).
Claim. By the maximality of P every point p ∈ P lies on at least two circles.
Proof of Claim. Clearly if some point p ∈ P lies on no circle, then we can move
it onto any circle Cq , q 6= p increasing U (P ) at least by one.
So assume every point lies on at least one circle, but there is a point p ∈ P
that lies on exactly one circle. We want to move p onto a crossing of some two
circles Cq , Cr with p 6= q, r. We take q to the rightmost point in P . And r to
be the rightmost point on Cq . Without loss of generality we can assume that
p 6= q, r. Since r lies to the left of q one of two points in Cq ∩ Cr lies to the
right of r. Thus by the choice of r this crossing is not occupied by any point in
P and we can place p there, increasing U (P ) at least by one.
Let us consider the n points and n circles as a topological drawing of some
graph G whose vertices are the points in P and whose edges are (drawn as)
the circular arcs between consecutive points on the circles. Going around every
circle we see that the edges of G corresponds one-to-one to the point-circle
incidences. Thus G has exactly 2U (P ) edges.
By the above claim G contains no loops (circles containing one point only).
But in general G is not simple. For example the point set in Figure 16 defines a
pair of vertices having a triple of edges between them. However, the maximum
edge multiplicity of G is four since at most two unit circles contain any given
pair of points. We get rid of all multiplicities by discarding at most 3/4 of the
edges of G. Denoting the resulting graph by G0 and its number of edges by m
we get m ≥ U (P )/2.

Figure 16: A point set defines a topological drawing of a graph where edges are
drawn as circular arcs which are subsets of unit circles centered at the points in
the set.

In case m ≤ 4n we immediately obtain U (P ) ≤ 8n which is less than 8n4/3 .

Otherwise, if m > 4n, we can apply the Crossing Lemma to the drawing of G0
and obtain

21
 1 m3 1 U (P )3
cr(G0 ) ≥ 2
≥ . (9)
64 n 512 n2
On the other

hand any two circles can cross at most twice, which gives
cr(G0 ) ≤ 2 n2 ≤ n2 . Together with (9) we obtain U (P )3 ≤ 512n4 and hence
U (P ) ≤ 8n4/3 .
It remains open to determine the asymptotic growth of U (n). Erdős had
offered $500 for a proof or disproof of his conjecture.
Conjecture 2.1 (Erdős [Erd46]).
U (n) = O(n1+c/ log log n )
Interestingly, the considerations of unit distances in the plane can be trans-
ferred into the notion of graphs. A unit distance graph is a graph that can be
drawn in the plane with edges being straight-line segments of unit length. A
matchstick graph is a graph that can be drawn in the plane with edges being
straight-line segments of unit length and without crossings. See Figure 17 for
some examples.

Figure 17: Four unit distance graphs, one of which is a matchstick graph.

Of course, the quantity U (n) can be seen as the maximum number of edges
in an n-vertex unit distance graph. Another interesting open question asks for
the chromatic number of unit distance graphs, i.e., the minimum number of
colors required to color the vertices of any unit distance graph so that vertices
that share an edge receive distinct colors. The Moser spindle (the third graph
in Figure 17 from the left) shows that some unit distance graphs require at least
4 colors.
An upper bound on the maximum chromatic number of unit distance graphs
can be obtained by coloring the entire plane so that every two points at distance
exactly 1 receive distinct colors. More precisely, we color the infinite graph P 2 =
(R2 , E) whose vertices are the points in the plane and whose edges correspond
to pairs of points at unit distance. The least number of colors in such a coloring
is called the chromatic number of the plane, denoted by χ(R2 ). Determining
the chromatic number of the plane was stated as a problem in 1950 by Edward
Nelson and is today known as the Hadwiger-Nelson problem. Since already
some unit distance graphs require 4 colors, we have χ(R2 ) ≥ 4. On the other
hand Figure 18 shows a proper coloring of P 2 with 7 colors. Thus we have
4 ≤ χ(R2 ) ≤ 7.
Amazingly, nobody was able to improve these bounds for 60 years now.
According to de Bruijn and Erdős [dBE51] the Hadwiger-Nelson problem,
i.e., determining χ(R2 ), and determining the maximum chromatic number of
unit distance graphs are equivalent, under the assumption of the axiom of choice.

22
Figure 18: A coloring of the plane with 7 colors such that points at unit distance
are colored differently and an induced coloring of the Moser spindle.

23
3 The Sliding Game
We begin with a quote.

‘ ‘Sam Loyd (1841–1911) was one of the greatest puzzle designers

of all times. Was he a mathematician? Certainly not, but he
could have become a great one.”
(János Pach 2009)

The puzzles that Pach is referring to are mostly chess puzzles. Indeed
Sam Loyd invented over 10.000 chess puzzles, which he published in newspaper
columns (the first at the age of 14(!)) and books. He spend his life develop-
ing chess strategies, producing puzzles, running music stores, and inventing and
selling games. Certainly the most famous game invented by Loyd is the Fifteen
Puzzle shown in Figure 19. It consists of 15 squares carrying the numbers 1
through 15, lying in a four-by-four box. The goal is to use the one empty space
in the box to slide the squares one at a time from a given starting position to
the well-ordered position in which the numbers are increasing row by row.

Figure 19: The Fifteen Puzzle invented in the 1870’s by Sam Loyd.

The Fifteen Puzzle became very popular just like the Rubik’s Cube a hun-
dred years later. Actually nine out of ten people in Great Britain, the US and
Europe went a little crazy trying to solve the task Sam Loyd gave to the public.
He offered $1000 for anyone who can solve the Fifteen Puzzle from the initial
configuration that is obtained from the well-ordered one by swapping the square
labeled 14 and 15.

Problem 10.
Show that no one will ever be able to claim the $1000.

The Fifteen Puzzle has been generalized to arbitrary graphs by Kornhauser,

Miller and Spirakis [KMS84]. In the Sliding Game one is given a graph and a
number of labeled chips placed onto a subset of vertices, at most one chip at
each vertex. The goal is to reach a certain final configuration, i.e., a placement
of the chips, by applying a number of sliding moves. In each move a chip is
send along an edge to a vertex that does not yet has a chip on it. So the Fifteen

24
Puzzle is equivalent to the Sliding Game with 15 labeled coins on the 4 × 4
square grid.
The problem of deciding whether a certain final configuration is reachable
from a certain initial configuration, and if so, finding a set of few moves doing the
job, has applications in memory management in distributed computing systems,
as well as, motion planning, e.g., for robots.
Here we want to analyse the variant of the Sliding Game with unlabeled
chips. Consider a given connected graph G = (V, E). Let S1 and S2 be two
k-element subsets of vertices of G, i.e., S1 , S2 ⊆ V , |S1 | = |S2 | = k. Note that
the set S1 ∩ S2 may be non-empty. Imagine a chip is placed at each vertex in
S1 and we want to move these k chips into the positions given by S2 . If a chip
lies at a vertex v and no chip lies at some vertex w, then a move from v to w is
defined as sliding the chip from v to w along a v, w-path (not only an edge) in
G of which no intermediate vertex is occupied by a chip, if any such path exists.
Theorem 3.1. In any connected n-vertex graph one can get from any k-element
initial configuration (k ≤ n) to any k-element final configuration in at most k
moves.
Proof. We prove the result by induction on k. The induction base k = 0 (or
k = 1 if preferred) is immediate. So let k ≥ 1.
Let S1 , S2 be the initial and final configuration, respectively. Let T be a
smallest (inclusion-minimal) tree in the graph containing all vertices in S1 ∪ S2 .
Then every leaf of T lies in S1 ∪ S2 . Let v be a leaf.
• Case 1: v ∈ S1 ∩ S2 – We remove the vertex v from T, S1 and S2 . Since
v is a leaf T \ v is again a tree and hence connected. Moreover, |S1 \ v| =
|S2 \ v| = k − 1. Now the result follows by applying induction to T \ v and
S1 \ v, S2 \ v.
• Case 2: v ∈ S1 \ S2 – Choose a path P in T connecting v to a vertex
w ∈ S2 such that no intermediate vertex of P belongs to S2 . Applying
induction to T \ v and S1 \ v, S2 \ w we obtain a sequence of at most k − 1
moves bringing all vertices in S1 \ v into the positions given by S2 \ w.
Thus the path P contains besides v and w no vertices from S1 ∪ S2 . In
particular there is a move from v to w.
• Case 3: v ∈ S2 \ S1 – This case is symmetric to Case 2.
We remark that the above induction not necessarily performs the optimal (min-
imum) number of moves.

3.1 The Geometric Sliding Game

Now let us consider the following geometric version of the Sliding Game. Con-
sider a set of k pairwise disjoint, objects in the plane. With objects we mean
“nice” subsets of R2 , namely closed, bounded and path-connected2 subsets such
as disks (“coins”) or segments (“matchsticks”). These objects need to be brought
from an initial configuration S1 to a final configuration S2 by sliding moves. In
a move we allow to take an object and slide it, possibly while rotating it in a
subtle way, to another position without colliding with the other objects. In the
2 The set contains a path between any two of its points.

25
unlabeled version the objects are congruent to each other and we do not specify
which object needs to be brought to which position. In the labeled version we
have general objects (every two of which may be different) and we do specify
the final position of each such object.
The problem is not always feasible, that is, it may be that there exists no set
of moves bringing the objects from the initial to the final configuration. This
may happen in the labeled as well as the unlabeled version. Two such situations
are illustrated in Figure 20.

(a)

(b)

Figure 20: Two situations where the geometric Sliding Game is infeasible.

On the other hand it is easy to see that the geometric Sliding Game is always
feasible for congruent disks. Indeed, it is always feasible with convex objects
(labeled or not).

Theorem 3.2. Any set of k convex objects in the plane can be moved from any
initial configuration to any final configuration in at most 2k moves.
Proof. Let S1 and S2 denote the initial and final configuration of objects, re-
spectively. We bring the objects into the final positions in two phases, each
consisting of k moves. In the first phase we slide the objects, one by one, along
the vertical direction far down. Indeed, these moves are pure translations along
the vertical unit vector. In the second phase we slide each object into its final
position given by S2 .
All that needs to be shown is that in any configuration at least one object
can be moved vertically towards −∞ without colliding the other objects. If
this is possible for an object, one says that it can be separated in the direction
(0, −1).
Lemma 3.1. Given any set of k pairwise disjoint, convex bounded objects in the
plane, there is at least one object that can be separated in the direction (0, −1).
Proof of Lemma. Consider for each object a leftmost and rightmost point amd
shoot a vertical ray from each such point upwards. We define a walk along the

26
objects, starting from any point on the leftmost ray as follows. On ray corre-
sponding to leftmost points walk downwards. When reaching the end of the
ray walk in counterclockwise direction around the corresponding object until
encountering another ray. If this ray corresponds to some leftmost point, con-
tinue as before. Note that the walk is weakly x-monotone and at all times can
be seen from (0, −∞). See Figure 21 for an example.

Figure 21: A set of convex objects with a ray starting from a leftmost and
rightmost point of each object, and a walk along the objects. The object O can
be separated in the direction (0, −1).

The walk will encounter a ray corresponding to a rightmost point, at the

latest, when reaching the rightmost point of the rightmost object. When en-
countering the first rightmost ray the corresponding object O has been traversed
consecutively from a leftmost to a rightmost point in counterclockwise direction.
Now this object O can be separated in the direction (0, −1) because the walk
on O can be seen from (0, −∞) and O is convex.
Iteratively applying Lemma 3.1 we obtain a separation order of S1 and an-
other separation order of S2 . Now in the first phase the objects are translated
down according to the separation order of S1 , so that in their positions between
the two phases no two objects can be pierced by the same horizontal line. In
the second phase the objects are slided into their final position according to a
reverse separation order of S2 .
We remark that the last move in the first phase is unnecessary. Thus every
set of k convex objects can be reconfigured in at most 2k − 1 moves.

Problem 11.
Provide an instance of the geometric Sliding Game with k unlabeled convex
objects which require 2k − 1 moves for reconfiguration.

For congruent disks, the maximum number of moves needed is still unknown.
√
Bereg, Dumitrescu and Pach [BDP05] show that for k disks 3k 2 + O( k log k)
1
√
moves are always sufficient and (1 + 15 )k − O( k) moves are sometimes neces-
sary.

To end this chapter, we present Sam Loyd’s Juggler puzzle.

27
The clown after juggling with the five
triangular pieces of cardboard to at-
tract attention proceeds to cut one of
them into two pieces.
He then lays the six pieces upon the
top of the box and shows that they will
fit together and form a perfect square.
The pieces represent five right-angled
triangles, say one inch high by two
inches on the base, so you can readily
cut five similar pieces from paper and
then guess how to cut one of them so
that the six pieces will form a perfect
square.

28
4 Convexity
We introduce one of the most important concepts in combinatorial geometry:
Convexity. We start by presenting the standard notions and notations, as well
as, the three best-known theorems about convexity: Carathéodory’s Theorem,
Radon’s Lemma and Helly’s Theorem.
Definition 4.1 (Convexity).
A set X ⊆ Rd is convex if for every two points x, y ∈ X the segment xy is
entirely contained in X. In other words, X is convex if for any two points
x, y ∈ X and every real number λ ∈ [0, 1] we have λx + (1 − λ)y ∈ X.
We refer to Figure 22 for some examples of convex and non-convex sets in
the plane.

(a) (b)

Figure 22: (a) Three convex sets. (b) Two non-convex sets, each with two points
certifying non-convexity.

Note that the intersection of any (not necessarily finite) family of convex
sets is again convex. However, the union of two convex sets is “most likely”
not convex. For any set X ∈ Rd we define the convex hull of X, denoted by
conv(X), as the smallest (that is inclusion-minimal) convex set containing X.
Equivalently, \
conv(X) = Y, (10)
Y ⊇X,Y convex

i.e., the convex hull of X is the intersection of all convex sets containing X.
It is easy to see that the convex hull is indeed a hull operator (sometimes
called closure operator), namely that it enjoys the following properties for all
sets X, Y ⊆ Rd .

• conv(X) ⊇ X (conv is extensive)

• conv(conv(X)) = conv(X) (conv is idempotent)
• X ⊆ Y ⇒ conv(X) ⊆ conv(Y ) (conv is monotone)

Note that by (10) we have that conv(X) = X if and only if X is convex itself.
An alternative definition of the convex hull is given by convex combinations.
A point x ∈ Rd is a convex combination of points Pkx1 , . . . , xk ∈ R if there
d

exists non-negative real numbers λ1 , . . . , λk with i=1 λi = 1 such that x =

Pk
i=1 λi xi . Then for any set X we have

conv(X) = {x ∈ Rd | x is convex combination of finitely many points in X}.

29
That we can indeed restrict to convex combinations of very few points in
X (in the plane three points are already enough) is the statement known as
Carathéodory’s Theorem.
Theorem 4.1 (Carathéodory’s Theorem).
Let X ⊆ Rd . Then each point of conv(X) is a convex combination of at most
d + 1 points of X.
In the plane Theorem 4.1 says, that the convex hull of any set X is equal
to the union of all triangles with endpoints in X. If X is finite, one can even
restrict to a small subset of triangles by triangulating the points in X. We
won’t go into more details here and just refer to Figure 23 for an example. In
general there is many ways to triangulate the points in X, some of which we
will consider later.

Figure 23: Triangulating a finite point set X with 10 points. The convex hull
of X is the union of the 12 triangles with non-intersecting interiors.

Problem 12.
Prove Carathéodory’s Theorem. You may use Radon’s Lemma from below.

We continue with the second basic theorem about convex sets after Cara-
théodory’s Theorem.
Theorem 4.2 (Radon’s Lemma).
Every set P of d + 2 points in Rd contains two disjoint subsets P1 , P2 such that
conv(P1 ) ∩ conv(P2 ) 6= ∅.
Proof. The d+2 points p1 , . . . , pd+2 in P are affinely dependent, i.e., there exists
λ1 , . . . , λd+2 , not all zero, such that
d+2
X d+2
X
λi = 0 and λi pi = 0.
i=1 i=1

Thus we have
d+2
X X X
0= λi pi = λi pi − (−λi )pi .
i=1 i:λi >0 i:λi <0
Pd+2 P P
Moreover, since i=1 λi = 0 we have i:λi >0 λi = i:λi <0 (−λi ) = Λ. Together
we obtain a point x which is a convex combination of P1 = {pi : λi > 0} as well
as a convex combination of P2 = {pi : λi < 0}:
X λi X −λi
x= pi and x = pi
Λ Λ
i:λi >0 i:λi <0

30
Clearly, P1 and P2 are both non-empty and disjoint, which proves the statement.

In the plane, Radon’s Lemma amounts for simply checking the only two
possible situations, which are depicted in Figure 24.

Figure 24: The only two combinatorial different configurations of four points in
the plane and two disjoint subsets (black points and white points respectively)
with intersecting convex hulls.

The third, and probably most famous, combinatorial result about convex
sets is Helly’s Theorem.
Theorem 4.3 (Helly’s Theorem).
Let C be a finite set of convex sets in Rd . If any d + 1 of these sets have a
non-empty intersection, then all the sets have a non-empty intersection.
Proof. We proceed by induction on n = |C|. The case n ≤ d + 1 is immediate,
so assume that n ≥ d + 2 and consider the sets X1 , . . . , Xn in C.
For every i = 1, . . . , n the sets in C \ Xi satisfy the assumptions of Helly’s
Theorem and hence we conclude by induction T that all these sets have a non-
empty intersection. We fix a point pi ∈ j6=i Xj arbitrarily. This gives an
n-element point set P = {p1 , . . . , pn } in Rd with n ≥ d + 2. By Radon’s Lemma
(Theorem 4.2) there exist disjoint subsets P1 , P2 of P such that conv(P1 ) ∩
conv(P2 ) 6= ∅.
We pick a point x in this intersection and claim that x ∈ Xi for all i =
1, . . . , n.
Helly’s Theorem is no longer true for collections C of infinitely many convex
sets. Already in R1 , i.e., on the real line, there are sets of infinitely many
intervals such that any finite subset of these have a non-empty intersection but
there is no point contained in each and every interval. For example consider
C = {(0, 1/n) | n ∈ N} or C = {[n, ∞) | n ∈ N}. However, for compact (meaning
bounded and closed) convex sets, Helly’s theorem remains true even if C consists
of infinitely many sets.
Inspired by Helly’s Theorem (Theorem 4.3) we make the following defini-
tions. Let P be a hereditary property of sets in Rd , meaning that if a family F
has property P then so has every F 0 ⊆ F. Examples for hereditary properties
are
• having a non-empty intersection,
• containing a set from a certain class of sets in the common intersection,
• being contained in an affine subspace of dimension d − 1,
• being pairwise disjoint.

31
Definition 4.2 (Helly number).
A family C of sets in Rd is said to have Helly number k with respect to a
hereditary property P if k is the smallest positive integer for which the following
is true for every finite subfamily F ⊆ C:
If every subset A ⊆ F of size |A| ≤ k has property P , then so has F.
So Helly’s Theorem says that the family of all convex sets in Rd has Helly
number d + 1.

Problem 13.
Determine the Helly number of family C and property P in each of the
following cases:
• C is the family of all axis-aligned boxes in R2 and P is “having a
non-empty intersection”.

• C is the family of all convex sets in R2 and P is “having a translated

copy of a fixed convex set X 6= ∅ in the intersection”.
• C is the family of all convex sets in R2 and P is “having some ray in
the intersection”.

• C is the family of all closed convex sets in R2 and P is “the intersection

fits between two parallel lines at distance 1”.

4.1 Sets of Constant Width

The following is an interesting and equally important question. For example,
think of the reconstruction of 3-dimensional objects from 2-dimensional scans
such as X-rays or Magnetic Resonance Imaging.

“Can a convex d-dimensional object be recovered from all its

(d − 1)-dimensional projections?”

Let us consider the above question in the plane (for d = 2). So let X ⊆ R2
be a convex set. For any a, b ∈ R the projection of X onto the line `(a, b) =
{(x, y) ∈ R2 | ax + by = 0} is a (open, closed, or half-open) segment denoted by
X|`(a,b) . For bounded X the width of X in direction (a, b) is the length of the
segment X|`(a,b) . See Figure 25 for an example.

Problem 14.
Show that if X ⊆ R2 is a compact convex set and p ∈ X is any point, then
there exists a, b ∈ R and a segment sa,b (p) with the following properties.
• sa,b (p) is parallel to `(a, b).

• p is contained in sa,b (p) and sa,b (p) is contained in X.

• The length of sa,b (p) is the width of X in direction (a, b).

32
 X `(1, −1)

`(0, 1)

`(1, 0)

Figure 25: A bounded convex set X and its projections to the lines `(1, −1),
`(0, 1) and `(1, 0).

For d = 2 the above question translates into the following. Can a bounded
convex set X in the plane be recovered from all its widths? Clearly, if X is not
closed, then its closure defines the same widths. But (maybe surprisingly) the
answer for closed sets is also NO. Even in the most simple case, when all the
widths are the same, there is infinitely many sets defining these widths.

Definition 4.3 (Set of Constant Width).

A compact (meaning bounded and closed) convex set X in the plane is a set of
constant width w if for every a, b ∈ R the width of X in direction (a, b) equals
w.

Since by appropriate scaling we can assume that w = 1 we often omit to

specify the width w and simply call those sets sets of constant width. Figure 26
shows some examples of sets of constant width. Such sets can be constructed
as follows.

Reuleaux polygons: Start with a regular n-gon P with n odd. Draw a cir-
cular arc between any two consecutive points of P with center being the
point opposite on P . The convex hull of all these arcs is a set of constant
width. Figure 26(a) shows Reuleaux polygons for n = 3 and n = 5.

Based on a triangle: Consider three distinct lines `1 , `2 , `3 , not all concur-

rent, no two being parallel. For every crossing point pij = `i ∩ `j draw a
circular arc with center pij between the rays of `i and `j containing an-
other crossing point and a second circular arc between the rays of `i and
`j not containing any other crossing point. Choose the radii so that these
six circular arcs meet with their endpoints in a cyclic way. Depending on
the triangle you may choose one or more radii to be 0. The convex hull of
the six circular arcs is a set of constant width. See the top and middle of
Figure 26(c) for two examples.
Based on a convex curve: Consider two opposite points on a w × w square,
one on the left and one on the right. Draw a convex curve γ between
these points so that γ is tangent to the bottom side of the square and at
all points the curvature of γ is at least the curvature of a circle of radius
w. Next, consider all segments of length w standing orthogonally on γ

33
 pointing up. The union of all these segments is a set of constant width w.
See the bottom of Figure 26(c) for an example.

(a) (b) (c)

Figure 26: (a) Three sets of constant width: The ball (top), the Reuleaux
triangle (middle) and the Reuleaux pentagon (bottom). (b) Some examples
of non-circular coins. (c) Constructing a set of constant width on basis of an
isosceles triangle (top), a general triangle (middle) and a half-ellipse inscribed
in a square (bottom).

In particular the Reuleaux polygons are used to design coins, see for example
Figure 26(b), because coins are recognized by coin-operated machines only based
on their width, weight and/or engraving at the rim. Non-circular coins are
introduced amongst other reasons to save raw materials. The set of constant
width w that has the smallest area was determined by Blaschke and Lebesgue
in the 1910’s.
Theorem 4.4 (Blaschke [Bla15], Lebesgue [Leb14]).
Among all sets of constant width w, the Reuleaux triangle minimizes the area.
Note that no two distinct sets of constant width w are contained in another.
And it is not visible to the naked eye that the area of the Reuleaux triangle
is less than the area of the ball. Indeed, as of today the 3-dimensional set of
constant width with minimum volume is still unknown.
Another 50 years before the Blaschke-Lebesgue Theorem, in 1860, the 21-
years old Frenchman Emile Barbier proved that the perimeter of all sets of
constant width w is the same as that of the circle of diameter w.
Theorem 4.5 (Barbier [Bar60]).
Every set of constant width w has perimeter πw.
To prove Barbier’s Theorem let us first introduce Buffon’s needle problem.
In 1777 Georges Louis Leclerc, Comte de Buffon, asked the following question.

34
 “Suppose you drop a needle on ruled paper, where the needle is shorter than
the distance between the lines on the paper. What is the probability that the
needle comes to lie in a position where it crosses one of the lines?”

The needle problem can be solved by evaluating a suitable integral, which

would also solve the problem for a long needle. However, Emile Barbier’s proof
uses a very elegant method in probabilistic geometry.
Theorem 4.6. If a needle of length ` is dropped on ruled paper with distance
d ≥ ` between the lines, then the probability that the needle comes to lie in a
position where it crosses one of the lines is exactly
2`
p= .
πd
Proof. Clearly if we drop a needle of length `, no matter the distance between
the lines, then the expected number of lines that it crosses is
X
E(`) = i · pi ,
i≥0

where pi denotes the probability that the needle crosses exactly i lines. Now if
we write ` = x + y then we get

E(x + y) = E(x) + E(y), (11)

because each crossing of the needle is produced with probability 1 either by the
front part of length x or by the back part of length y. From (11) we can derive
E(nx) = nE(x) for all n ∈ N, which implies mE( m n
x) = E(m mn
x) = E(nx) =
n
nE(x). Thus for all rational number r = m holds E(rx) = rE(x). Because
E(x) is monotone, we conclude that

E(x) = cx for all x ≥ 0 and some constant c = E(1). (12)

Now note that (11) did not use the fact that the front part and the back
part are aligned to one longer straight segment. Indeed the same holds if front
and back are glued with their ends in any angle. And the same holds if the
needle is a general polygonal line with any number of straight segments. If its
total length is `, then the expected number of crossings with the lines is exactly
E(`) and (12) still holds.
Finally we may even consider a curved needle by approximating it with
polygonal lines of the same length but with more and more segments. In the
limit, E(`) still gives the same number for any arbitrary curve of length `. In
particular, we can consider a needle that is a perfect circle of diameter d. Such a
needle has length πd and, more importantly, if it is dropped it produces exactly
two crossings no matter where it comes to lie. We conclude
2
E(πd) = 2 and thus c= .
πd
Together with E(`) = p1 , provided ` ≤ d, this proves the theorem.

35
 Figure 27: Dropping needles and circles on ruled paper at random.

Proof of Barbier’s Theorem. Consider any set X of constant width w. To prove

that X has perimeter πw, it is now sufficient to note that in the above proof
a needle that forms the boundary of X produces exactly two crossings with
equally spaced lines at distance w. Thus the length ` of the needle, which is
also the perimeter of X, satisfies
2 `
= E(`) = 2.
πw
In other words ` = πw.
For more on sets of constant width, including how to drill a square hole with
the Reuleaux triangle and 3-dimensional sets of constant width, we refer to the
short survey of Kawohl [Kaw09].

Next let us focus on more discrete problems with convexity. In particular,

we are interested in finite point sets X in Rd ; of course with strong preference
for the case d = 2. Given a finite point set X ⊂ Rd its convex hull conv(X)
is called a polytope. We will always assume that conv(X) is full-dimensional,
i.e., it is not contained in any (d − 1)-dimensional hyperplane. Let us fix some
notations. We refer to Figure 28 for examples illustrating these definitions.

• A point p ∈ conv(X) is called a corner of conv(X) if

p∈
/ conv(X \ p).

In particular, the set of all corners of conv(X) is a subset X̄ of X.

• A finite set X ⊂ Rd is said to lie in convex position if

every x ∈ X is a corner of conv(X).

Equivalently, X is the set of all corners of some polytope in Rd .

• A (d − 1)-dimensional hyperplane h is called a supporting hyperplane of
conv(X) if there is a closed half-space H defined by h such that

conv(X) ⊆ H and |h ∩ X̄| ≥ d.

Equivalently, h ∩ conv(X) is a (d − 1)-dimensional set contained in the

boundary of conv(X).

36
 h

conv(X) X̄ ⊆ X

H
(a) (b) (c)

Figure 28: (a) The convex hull of finitely many points is a polytope. (b) The
set of corners of conv(X) is a subset X̄ of X. (c) A supporting hyperplane h
contains at least d corners of conv(X).

In the plane, i.e., when d = 2, polytopes are also called convex polygons, or
simply polygons when convexity is given from the context. For a convex polygon
P = conv(X) the supporting hyperplanes are simply lines and the intersection
of a supporting line ` with P is called an edge of P . Clearly, every convex
polygon has as many edges as corners.

Problem 15.
Consider a compact convex set X in the plane, a number α ∈ (0, π] and
the locus Lα of all points that can see X with an α aperture angle. See
Figure 29 for an illustration.
a) For which values of α is Lα the boundary of some convex set?

b) Describe the shape of Lπ/2 in case X is a convex polygon.

X α
q

α
p

Figure 29: A compact convex set X in the plane and two points p and q that
see X with an α aperture angle with α = π/2.

37
 Problem 16.
Consider a convex polygon P in the plane and a number t strictly greater
than the area of P . For each point q ∈
/ P let P (q) be the polygon conv(P ∪
{q}).

a) Prove that the locus Lt of all points q for which the area of P (q)
equals t is the boundary of a convex polygon enclosing P .
b) Prove that if P has n corners, then Lt has between n and 2n corners.
When does Lt have less than 2n corners?

4.2 Centerpoints
Let X be a finite set of points in the plane. Let us think of which points of
Rd are very “central” in X or lie “deep” within X. Intuitively, a point is deep
within X if it cannot be reached from the outside (say Rd \ conv(X)) without
passing through many (say half or one third) other points of X. We present two
attempts to formalize this intuition. In especially, we investigate the concepts
of centerpoints of X; once with respect to half-spaces and once with respect to
quadrants.
Definition 4.4 (Half-Space Centerpoint).
A half-space centerpoint of a set X of n distinct points in Rd is a point x ∈ Rd
n
for which each closed half-space that contains x contains at least d+1 points from
X.
For d = 1 the set X is just a set of n real numbers {r1 , . . . , rn } and a half-
space centerpoint corresponds to a number r that is less than or equal to half
of the numbers in X and greater than or equal to half of the numbers in X.
Indeed, in this case we can always pick r from the set X. If |X| = n is odd, then
we even have to pick such r from X. Such a half-space centerpoint (number) of
a 1-dimensional finite set (set of numbers) is better known as the median of X.
For d > 1 there are cases in which no half-space centerpoint belongs to X.
For example, consider X to be any set of n points on a circle C ⊂ Rd . Then for
every point x ∈ X we can find a closed half-space H, e.g., one that lies tangent
on C at x, that contains x but no second point from X. See Figure 30(a) for
an illustration.
The fact that every finite point set in Rd has a half-space centerpoint was
proven by Rado in 1946 [Rad46] and is today known as the Centerpoint The-
orem. Since we will need it later, we include a “moreover” statement for the
2-dimensional case.
Theorem 4.7 (Centerpoint Theorem).
For every finite point set X in Rd there exists a half-space centerpoint p.
Moreover, if d = 2 then p can be chosen to be a point of X or as the inter-
section of two segments with endpoints in X.
Proof. Let X be any set of n points in Rd . First note that x ∈ Rd is a half-
space centerpoint if and only if x lies in every open half-space H with |X ∩ H| >
d d
d+1 n. Let HX = {H : H open half-space with |X ∩ H| > d+1 n}. Hence, we

38
 Q2 (p)

p
x
H

Q4 (p)
(a) (b)

Figure 30: (a) If X is any set of n points on a circle, then no point of X is an

α-half-space centerpoint for α > 1/n. (b) If X is a set of n equidistant points
on a circle, then no point of R2 is an α-quadrant centerpoint for α > 1/4 + 1/n.

have
T to show that the intersection of all these half-spaces is non-empty, i.e.,
H∈HX H 6= ∅. However, we cannot use Helly’s Theorem directly since we have
infinitely many half-spaces all of which are open and unbounded.

T
H AH
AH = conv(X ∩ H) H ∈ HX
(a) (b) (c)

d
Figure 31: (a) A half-space H containing more than d+1 n points from a set X
of n points. (b) The corresponding convex compact set AH = conv(X ∩ H). (c)
The intersection of all AH with H ∈ HX is a convex polytope.

Instead, we consider for each half-space H ∈ HX the set AH = conv(X ∩H),

which is convex and compact. See Figure 31(a)-(b) for an illustration. Moreover,
d
there is only finitely many of them. Every AH contains more than d+1 n points
from X, so the intersection of any d + 1 of these AH contains at least one point
of X, i.e., is non-empty. By Helly’s Theorem (Theorem 4.3) there exists a point
x such that \
x∈ AH .
H∈HX
T
With AH ⊂ H for each H ∈ HX we conclude x ∈ H∈HX H, i.e., x is a
half-space centerpoint of X.
Finally observe that the intersection of all AH with H ∈ HX is a convex
polytope because there are finitely many AH each of which is a convex polytope.
Choosing in case d = 2 the half-space centerpoint p to be a corner of this
polytope (it is a polygon now) we see that either p ∈ X or p is the intersection
of two edges from distinct AH . Since every edge of every AH is a segment with

39
endpoints in X we get that in the latter case p is the intersection of two such
segments. See Figure 31(c) for an example.
1
The fraction d+1 in the definition of a half-space centerpoint is the maximal
number for which the Centerpoint Theorem (Theorem 4.7) still holds. Indeed,
every set X of d + 1 affinely independent points in Rd has no “α-half-space
1
centerpoint” for α > d+1 .
Recall that Radon’s Lemma (Theorem 4.2) states that every set of d + 2
points in Rd can be partitioned into two sets such that the convex hulls of these
sets intersect, meaning that they have a non-empty intersection. Now suppose
we want to partition our point set not only into two sets but r sets whose r
convex hulls mutually intersect. Let us call such a partition a good r-partition.
For example, Figure 32(a) shows two good 3-partitions of the same set of seven
points in the plane. It is not difficult to see that if we increase the number of
points (formally d + 2 in Radon’s Lemma) to some high enough number than
such a good r-partition always exists.

(a) (b)

Figure 32: (a) Two good 3-partitions of the same set of seven points in the
plane. (b) A set of six points in the plane with no good 3-partition.

It is also not very hard to come up with examples of sets of 2d + 2 points

in Rd that have no good 3-partition. Indeed, Figure 32(b) shows a set X of six
points in the plane with no good 3-partition. Since the points in X are in convex
position each set in any good r-partition must contain at least two points and
hence all sets in a good 3-partition must consist of exactly two points. However,
no three of the fifteen segments with endpoints in X intersect in a common
interior point, which implies that no good 3-partition exists.
In general one requires more than (r − 1)(d + 1) points in Rd in order to
guarantee the existence of a good r-partition. That (r − 1)(d + 1) + 1 points
are indeed always sufficient for a good r-partition was proven by Tverberg in
1966 [Tve66]. He also published a better proof in 1981 [Tve81] and yet another
one together with Vrećica in 1993 [TV93].
Theorem 4.8 (Tverberg’s Theorem).
Every set X of (r − 1)(d + 1) + 1 points in Rd can be partitioned into r disjoint
non-empty sets X1 , . . . , Xr such that

conv(X1 ) ∩ · · · conv(Xr ) 6= ∅.

Note that setting r = 2 we obtain Radon’s Lemma (Theorem 4.2). We omit

a proof of Tverberg’s Theorem in full generality here. Instead let us present a
short and elegant proof for the case d = 2.

40
Proof of Tverberg’s Theorem in d = 2 dimensions.
We have to show that every set X of n = 3r − 2 points in the plane can be
partitioned into r subsets X1 , . . . , Xr such that there is a point p in the convex
hull of each Xi , i = 1, . . . , r.
Somehow strangely, we first identify p and afterwards the sets X1 , . . . , Xr .
We choose p to any half-space centerpoint for X with the additional property
that either p ∈ X or p = conv(x1 , x2 ) ∩ conv(x3 , x4 ) for some x1 , x2 , x3 , x4 ∈ X.
The existence of such a point p is guaranteed by the Centerpoint Theorem
(Theorem 4.7). In the first case, i.e., when p ∈ X, we define Xr = {p}. In the
second case we define Xr = {x1 , x2 } and Xr−1 = {x3 , x4 }. In either case we
are left with a set X 0 of 3k points from X that are yet to be partitioned into k
sets, with k ∈ {r − 1, r − 2}.

x1 2
x4
1 3
10 p 4
9
5
x3
7
8 x2
(a) (b)

Figure 33: (a) A set X of n = 3r − 2 = 13 points in the plane, a half-space

centerpoint p of X of the form p = conv(x1 , x2 ) ∩ conv(x3 , x4 ), and a numbering
of the points in X 0 = X \ {x1 , x2 , x3 , x4 } according to their cyclic order around
p. (b) An r-good partition of X.

Next we number the points in X 0 from 1 to 3k according to their cyclic order

around p – say clockwise around p. In case two or more points of X 0 lie on the
same ray emanating from p we give these points consecutive numbers in any
way. See Figure 33(a) for an example. For i = 1, . . . , k we define the set Xi to
be the triple of points from X 0 whose numbers equal i + 1 modulo k. We claim
that for every i = 1, . . . , k the convex hull of Xi contains the point p, which will
prove the claim. We refer to Figure 33(b) for an example.
So assume for the sake of contradiction that p ∈ / conv(Xi ) for some i ∈
{1, . . . , k}. Then p and conv(Xi ) can be separated by some line `, i.e., one half-
space H defined by ` contains p and no point from Xi . (In case k = r − 2 we
may choose without loss of generality ` to be not parallel to the segments x1 x2
and x3 x4 .) Since p is a half-space centerpoint of X the half-space H contains
at least d n3 e = d 3r−2
3 e = r points from X, at most r − k of which are not in
X 0 . Thus H contains at least k points from X 0 and hence at least one of these
points has a number equal to i modulo k – a contradiction to the assumption
that the H ∩ Xi = ∅.

Next we define another variant of a centerpoint, this time with respect to quad-
rants. We focus on the case d = 2 first. For a point p = (px , py ) ∈ R2 the four

41
quadrants centered at p are defined as the sets

Q1 (p) = {(x, y) ∈ R2 | px ≤ x and py ≤ y},

Q2 (p) = {(x, y) ∈ R2 | px ≥ x and py ≤ y},
Q3 (p) = {(x, y) ∈ R2 | px ≥ x and py ≥ y},
Q4 (p) = {(x, y) ∈ R2 | px ≤ x and py ≥ y}.

In particular, each quadrant Qi (p) is closed, axis-aligned and has apex p, i =

1, 2, 3, 4. The pairs of quadrants {Q1 (p), Q3 (p)} as well as {Q2 (p), Q4 (p)} are
called opposite quadrants at p. In order to get points that are indeed central for
the set X we seek points that contain many points of X in both quadrants of at
least one pair of opposite quadrants. For convenience, we define these quadrant
centerpoints for general reals α ∈ [0, 1].
Definition 4.5 (Quadrant Centerpoint).
Let X be a finite set of n distinct points in the plane and α ∈ [0, 1]. An α-
quadrant centerpoint is a point x ∈ R2 for which there exist two opposite quad-
rants Qi (x), Qi+2 (x) at x (i ∈ {1, 2}) each of which contains at least αn points
from X.
Similarly to Theorem 4.7 we want to determine the maximum α for which
every set X of n points in the plane has an α-quadrant centerpoint. Note that
without loss of generality we can assume that no two points have the same x-
or y-coordinate. This is because we consider closed quadrants and moving one
of two axes-aligned points p, q slightly in diagonal direction just decreases the
number of incidences q ∈ Qi (p) and p ∈ Qi (q) for i = 1, 2, 3, 4. Indeed we may
assume that the n points of X lie on the vertices of an n × n square grid such
that no two lie in the same column or row.
By considering n equidistant points on a circle (see Figure 30(b)) we see
that no point of the plane is an α-quadrant centerpoint with α > 1/4 + 1/n.
Hence the maximum α we seek is at most 1/4 and it turns out that this value
is already the truth.
Proposition 4.1. For every finite point set in R2 there exists a 1
4 -quadrant
centerpoint. This is best-possible.
Proof. Fix X to be any set of n points in the plane. Let `v be a vertical line such
that both half-spaces defined by `v contain at least d n2 e points of X. Further
let `h be a horizontal line such that both half-spaces defined by `h contain at
least d n2 e points of X. Note that if n is odd, then `v and `h contain some point
of X and that it may be the same point. See Figure 34 for an illustration.
We claim that the point p = `v ∩ `h is a 41 -quadrant centerpoint of X. By
the definition of `v and `h we have

|Q1 (p) ∩ X| + |Q4 (p) ∩ X| ≥ n/2,

|Q2 (p) ∩ X| + |Q3 (p) ∩ X| ≥ n/2

and

|Q1 (p) ∩ X| + |Q2 (p) ∩ X| ≥ n/2,

|Q3 (p) ∩ X| + |Q4 (p) ∩ X| ≥ n/2.

42
 p
`h

`v

Figure 34: A set X of n = 13 points and the lines `h and `v whose half-spaces
contain d n2 e = 7 points each. The point p where `h and `v intersect is a 1/4-
quadrant centerpoint of X.

If each of |Qi (p) ∩ X| (i = 1, 2, 3, 4) is at least n/4 we are done by choosing two

opposite quadrants at p arbitrarily. Hence we may assume by symmetry that
|Q1 (p) ∩ X| < n/4. But this implies |Q2 (p) ∩ X| > n/4 and |Q4 (p) ∩ X| > n/4,
i.e., p is a 14 -quadrant centerpoint of X.

The 1/4-quadrant centerpoint constructed in the proof of Proposition 4.1

may or may not be contained in X. Moreover, there is examples where every
1/4-quadrant centerpoint is not in X. However, we do not lose to much if we
restrict our attention to points in X. As we pointed out earlier, this is in sharp
contrast to half-space centerpoints.

Theorem 4.9 (Brönnimann, Lenchner, Pach [BLP07]).

Every finite point set X in the plane contains a point x ∈ X that is a 1/8-
quadrant centerpoint of X.
If the points in X are in convex position then there exists x ∈ X that is a
1/4-quadrant centerpoint of X.

We present here the shorter proof taken from [ABDF+ 11]. It derives Theo-
rem 4.9 as an immediate consequence of the following lemma.
Lemma 4.1. Every set X of n points in the plane contains a point x ∈ X such
that
n
min(|Q1 (x) ∩ X|, |Q3 (x) ∩ X|) + min(|Q2 (x) ∩ X|, |Q4 (x) ∩ X|) ≥ .
4
Proof. Consider the sets XT , XB , XL and XR of the first bn/4c points of X
from the top, the bottom, the left and the right, respectively. Each set Xi with
i ∈ {T, B, L, R} is associated with a horizontal or vertical line `i that contains a
point of Xi and separates the set Xi from its complement X \ Xi . See Figure 35
for an illustrative example.
It follows that there is a point x ∈ X in the intersection of the four “larger”
half-spaces defined by `T , `B , `L and `R , namely the closed half-spaces contain-
ing d 43 ne points of X each. Denoting this intersection by R we claim that every
point x ∈ R ∩ X satisfies the claimed inequality.
Let x be such a point and assume that min(|Q1 (x) ∩ X|, |Q3 (x) ∩ X|) =
|Q1 (x)∩X| = k. Since XT is contained in Q1 (x)∪Q2 (x) it follows that |Q2 (x)∩

43
 `T

`B

`L `R

Figure 35: A set X of n = 29 points, the lines `T , `B , `L , `R , and the region R.

X| ≥ n/4 − k. Considering XR we obtain |Q4 (x) ∩ X| ≥ n/4 − k. Consequently,

min(|Q1 (x) ∩ X|, |Q3 (x) ∩ X|) = k

and
min(|Q2 (x) ∩ X|, |Q4 (x) ∩ X|) ≥ n/4 − k,
which proves the lemma.
Proof of Theorem 4.9.
From Lemma 4.1 we get a point x ∈ X with

min(|Q1 (x) ∩ X|, |Q3 (x) ∩ X|) + min(|Q2 (x) ∩ X|, |Q4 (x) ∩ X|) ≥ n/4.

For part one of the theorem it is enough to observe that at least one of the
minima is at least n/8.
For the second part note that if X is in convex position one of the four open
quadrants centered at x contains no point from X. Therefore, one of the two
minima is zero and thus the other minimum is at least n/4.
Clearly, Figure 30(b) shows that the second part of Theorem 4.9 is best-
possible. For the first part consider a set X of n = 8k points (k ∈ N) that
comes in 8 sets of k collinear points each as illustrated in Figure 36. It is
straight-forward to check that X does not contain an α-quadrant centerpoint
for any α > 1/8.
The restriction to axes-aligned quadrants in the definition of α-quadrant
centerpoints may seem to be artificial. It surely makes sense to define a general
α-quadrant centerpoint of a set X of n points in the plane as a point p ∈ R2
such that there exists a pair of opposite quadrants centered at p defined by two
perpendicular lines through p, each if which contains at least αn points of X.
Indeed, Figure 30(b) shows that Proposition 4.1 remains still true and best-
possible, even when considering general α-quadrant centerpoints. On the other
hand, the first part of Theorem 4.9 can be improved slightly. In [BDPZ10] Ben-
Dan, Pinchasi and Ziv show that every finite point set X in the plane contains a
point x ∈ X which is a general α-quadrant centerpoint for X with α = 81 + 8·391
.

44
Figure 36: A set X of n = 8·6 points in the plane none of which is an α-quadrant
centerpoint for α > 1/8.

The best known upper bound is 1/7, obtained by suitably placing n/7 points
on each of 7 rays emanating from the origin with an angle of 2π/7 between
consecutive rays.

Problem 17.
(Research Problem)

Prove that there exists some α > 1/8 such that every finite point set X in
the plane contains a point x ∈ X that is a general(!) α-quadrant centerpoint
of X.

For other interesting variant of quadrant centerpoints, including the higher-

dimensional cases, we refer to [ABDF+ 11].
In the next section, we consider two finite point sets X, Y in R2 (in general
it would be d sets in Rd ). We will try to find a line (in general it would be a
(d − 1)-dimensional hyperplane) rather than a point that is “central” to both
point sets. We consider finite point sets only, even though most of what follows
holds in a much more general setting, as will be mentioned later.

4.3 Ham Sandwiches

Although not closely related to convexity, let us next consider the Ham Sandwich
Theorem. Consider a ham sandwich in R3 , see Figure 37(a) for an example, i.e.,

45
some bread B ⊆ R3 , some ham H ⊆ R3 and some cheese C ⊆ R3 . A ham
sandwich cut is a cut of the ham sandwich with a straight motion of a knife so
that the bread as well as the ham and the cheese are cut into halves. In R2 we
consider two pancakes, a red one and a blue one, and call a straight cut that
halves either pancake a pancake cut. See Figure 37(b) for an example.

(a) (b)

Figure 37: (a) A ham sandwich cut. (b) A pancake cut.

More formally a compact d-dimensional set in X ⊂ Rd is said to be bisected

by a (d − 1)-dimensional hyperplane h if both half-spaces defined by h contain
half of the d-dimensional volume of X. The Ham Sandwich Theorem then states
that given any d such compact d-dimensional sets in Rd there exists a hyperplane
that bisects each of these sets at the same time.
Theorem 4.10 (Ham Sandwich Theorem).
Any d compact d-dimensional sets in Rd can be simultaneously bisected by a
(d − 1)-dimensional hyperplane.

Problem 18.
Consider 50 apples and 50 bananas being packed in 50 boxes in some way.
For example, there may be empty boxes, boxes containing 2 apples and 42
bananas, etc.
a) Prove that one can always pick at most 26 boxes such that these boxes
contain in total at least 25 apples and 25 bananas.
b) How do you have to pack the apples and bananas into the boxes so
that picking 50 boxes is not enough?
c) What about 50 apples, 50 bananas and 50 coconuts in 50 boxes?

If d = 2 the Ham Sandwich Theorem is also known as the Pancake Theorem.

It states that any two compact sets (or pancakes) in the plane can be simulta-
neously bisected by some line `. This means that both sets have half its area
on either side of `. We again refer to Figure 37(b) for an example.
The Ham Sandwich Theorem is usually proven as a consequence of the
Borsuk-Ulam Theorem from algebraic topology. Here we consider the discrete
version of the Ham Sandwich Theorem, which deals with d finite point sets in
Rd . Instead of the area as the underlying measure we now take the counting
measure, which is simply the number of points in each set. A (d−1)-dimensional

46
hyperplane h is said to bisect a finite set X ⊂ Rd if each open half-space defined
by h contains at most b|X|/2c points from X. Note that if |X| is odd and h
bisects X, then at least one point of X lies on h.
Theorem 4.11 (Discrete Ham Sandwich Theorem).
Any d finite sets in Rd can be simultaneously bisected by a (d − 1)-dimensional
hyperplane.
Proof of the Discrete Ham Sandwich Theorem in d = 2 dimensions.
We have to show that for any finite point set X and any finite point set Y in the
plane there exists a line ` such that each open half-space defined by ` contains
at most b |X| |Y |
2 c points of X and at most b 2 c points of Y .
We start with some line ` that bisects X. By rotating the plane we can
assume that without loss of generality that no two points in X have the same
x-coordinate. Then we choose ` to be a vertical line through some point p0 ∈ X
that has exactly b |X|
2 c points of X to the left.
Now we start rotating ` in counterclockwise direction around p0 . We will
abuse notation and always refer to the rotated line again as `, although these
are different lines in R2 . We rotate until ` hits some point in X \ p0 . Clearly,
one open half-space defined by ` (the “left” one) contains at most b |X|
2 c points
of x and the other open half-space (the “right” one) contains at most b |X|
2 c−1
points of X. See Figure 38 for an example3 .

x7 = xk

x6 = xk+1−i
p0
p2 x5
x4
p3 = p4 x3
p5
p1 x2 = xi

x1

(a) (b)

Figure 38: (a) Rotating a line such that at all times it bisects a point set X of
9 points in the plane. (b) Rotating across a set of k = 7 collinear points of X.

Note that ` may have hit more than one point from X. Let x1 , . . . , xk be the
points in ` ∩ X indexed as they appear along `. We have k ≥ 2 and p0 = xi for
some i ∈ {1, . . . , k}. We now consider the point p1 = xk+1−i and start rotating
3 Bonus question: What kind of set will the arrowed circular arcs in Figure 38(a) enclose

after a full rotation of the line?

47
` in counterclockwise direction around p1 instead of p0 . Note that p0 = p1 in
case i = (k + 1)/2. Considering the line ` shortly before hitting the second point
in X and shortly after starting the rotation around p1 we see that all points xj
with j = i + 1, . . . , k + 1 − i remain on the same side of ` while all points xj
with j < i or j > k + 1 − i switch the side of `. Since the number of points
switching from one side of ` to the other equals the number of points changing
sides in opposite direction ` again bisects X.
We continue rotating ` around p1 instead of p0 . This way we get a sequence
p0 , p1 , p2 , . . . of points around which ` is rotated. See Figure 38(a) for an illus-
trating example. At all times ` contains at least one point of X and bisects
X.
Now consider the time that ` is vertical again, i.e., after a rotation of π.
Clearly, ` bisects X and contains some point of X. If |X| is odd, this point
must be p0 , which means that ` is again in its initial position. If |X| is even, `
could be parallel but not identical to its initial position. In that case no point of
X lies strictly between the final and the initial position of ` and we continuously
slide ` from its final onto its initial position without passing through any point
if X.
In either case, we end up with ` being in the same position as in the very
beginning. But the sides of ` are swapped! Hence if initially the line ` had m
points of Y on its first side and |Y | − m points of Y on its second side, after a
rotation of π (and a possible shift) it has |Y |−m points of Y on its first side and
m points of Y on its second side. Thus at some intermediate step, ` must have
had at most b |Y2 | c points on each side and at this point in time ` was bisecting
X and Y simultaneously.
It is easy to verify that the Ham Sandwich Theorem is best possible in terms
of the number of sets that can be bisected simultaneously. Already in the dis-
crete 2-dimensional version there exist three sets that cannot be simultaneously
bisected by a single line `. Consider for example three sets each of which can
be separated from the other two by some line, see Figure 39(a). Secondly, there
is situations in which there is only one Ham Sandwich cut for two sets X and
Y , e.g., when all the points in X ∪ Y are collinear, see Figure 39(b).

(a) (b)

Figure 39: (a) Three sets in the plane that cannot simultaneously be bisected
by a single line. (b) Two sets in the plane for which there exists only one Ham
Sandwich cut.

The proof of the Discrete Ham Sandwich Theorem (Theorem 4.11) above
uses a sweep line argument that is very common in combinatorial problems on

48
planar point sets. Suppose we have to show the existence of a line ` that satisfies
two properties P1 and P2 . In the above case P1 was “bisecting X” while P2 was
“bisecting Y ”. The general idea is to start with a line ` that has property P1
and then rotate ` in discrete steps, maintaining property P1 for ` at all times.
If we can also prove that after a full rotation of ` at some intermediate step
it necessarily satisfies property P2 , then we are done. In particular, we have
proven the existence of a line ` satisfying properties P1 and P2 simultaneously.

Problem 19.
Prove that for every finite point set X in the plane there exists a point
p ∈ R2 and a pair of perpendicular lines `1 , `2 through p such that each
of the four quadrants centered at p defined by `1 and `2 contains at least
b|X|/4c points of X.

Sweep line arguments can also be used in non-discrete settings. However, the
line ` does not necessarily rotate in discrete steps around finitely many points
in the plane. For example Figure 40 shows the trace of the point around which
a line rotates while bisecting the area of an equilateral triangle at all times4 .
In this case one would rather prove that for all directions (a, b) there exists a
line ` parallel to `(a, b) satisfying property P1 . But even if this line changes
continuously in the direction (a, b) the trace of points around which ` is rotated
during such a continuous sweep can be a very complicated curve.

Figure 40: A line ` is continuously swept over an equilateral triangle so as to

halve the area of the triangle at all times. The trace of the rotation point p is
indicated.

Problem 20.
Let Q be some convex polygon.
• Prove that for every point p ∈ Q there is a line `p that contains p and
bisects the area of Q.

• Prove that there is a line ` that simultaneously bisects the area of Q

and the perimeter of Q.

4 The author would like to thank Sebastian Ziesche for his help in computing the trace.

49
4.4 Convex Independent Subsets
In this section we consider finite sets X of points in the plane in general position,
meaning that no three points in X are collinear. We are interested in finding a
subset of many points in X that lie in convex position, i.e., form the corners of
some convex polygon. This problem has already been considered 80 years ago
and still leads to interesting new results these days.
Let us start with an easy lemma.
Lemma 4.2. Every set of 5 points in the plane in general position contains a
convex quadruple.
Proof. Let X be a set of 5 points in the plane in general position. If conv(X)
has at least four corners, then any set of four corners form a convex quadruple.
Otherwise, conv(X) is a triangle and two points x1 , x2 ∈ X lie interior to it.
Since no three points are collinear the line through x1 and x2 separates one
corner of conv(X) from the other two, called x3 and x4 . Then {x1 , x2 , x3 , x4 } ⊂
X is a convex quadruple. See Figure 41 for an illustration.

Figure 41: All combinatorially different sets of 5 points in the plane in general
position and a convex quadruple (indicated by thick edges) in each of them.

Problem 21.
Find a set of 8 points in the plane in general position which does not contain
any convex pentagon.

By Lemma 4.2 all sets of five or more points in the plane contain a convex
independent subset of size 4. In general we would like to answer the following
question.
“Does every sufficiently large point set in the plane contain a convex
independent subset of prescribed size?”
The answer to above question is ’YES’ as proven by Erdős and Szekeres in 1935.
Theorem 4.12 (Erdős-Szekeres [ES35]).
For every k ∈ N there exists N ∈ N such that every set of n ≥ N points in the
plane in general position contains a convex k-gon.

Problem 22.
How large convex k-gons can you find among the points of the n × n square
grid? (It is enough to give the asymptotic growth.)

50
 This result (Theorem 4.12) is considered to be one of the first Ramsey-
type results in history, where a Ramsey-type question is loosely speaking the
following.
“Does every sufficiently large structure of a certain type contain a “regular”
substructure of prescribed size?”
Let us briefly mention the original Ramsey-type question considered by
Frank Plumpton Ramsey in 1928 (published in 1930 [Ram30]). Ramsey was
a young (he was born in 1903 in Cambridge) very talented mathematician,
philosopher and economist. After having mastered German, he moved to Vi-
enna at the age of 19, where he became a close friend of Ludwig Wittgenstein.
Ramsey translated Wittgenstein’s texts from German into English and later
convinced him to return to Cambridge where Wittgenstein once studied. Back
in Cambridge in 1924 Ramsey became Wittgenstein’s supervisor and provided
him with financial support. Ramsey died at the age of 26 from chronic liver
problems.
In mathematics Ramsey was mostly interested in logic, especially in first-
order logic and decidability problems. What is nowadays known as Ramsey’s
Theorem was actually just a lemma to prove decidability of a special class of
first-order logic. Based on this Alonzo Church later showed undecidability of
the decision problem in first-order logic in general, known as Church’s Theo-
rem [Chu36], answering Hilbert’s problem in the negative.
The setting of our question above that has been considered by Ramsey is a
very general one. To this end we consider the complete r-uniform hypergraph on
r r
N vertices KN , that is, the vertices of KN are the elements of some N -element
r
set V and the edges of KN are all r-element subsets of V . For example Figure 42
depicts the complete hypergraphs K62 (which is the same as K6 ) and K53 .

Figure 42: The complete 2-uniform hypergraph on 6 vertices K62 = K6 and the
complete 3-uniform hypergraph on 5 vertices K53 , each with one of its edges
highlighted.

Now in Ramsey’s Theorem the “arbitrary” but sufficiently large structure

is a coloring of the edges of some large r-uniform hypergraph with a bounded
number of colors. The size of such a structure is the number of vertices. And as
“regular” substructure we consider complete r-uniform sub-hypergraphs whose
edges are colored all the same, that is monochromatically. Ramsey’s theorem
states that if we want to find a monochromatic Knr inside every KN r
which is
colored with c colors, then we just have to make N large enough (depending on
n, r and c) and are guaranteed to find it.

51
Theorem 4.13 (Ramsey’s Theorem [Ram30]).
For every natural numbers n, r and c there exists an N ∈ N such that in every
r
coloring of the edges of KN with at most c colors we can find a subset of n
vertices all of which induced edges are colored the same, i.e., a monochromatic
copy of Knr in KN r
.
Given n, r and c the minimum N for which Ramsey’s Theorem holds is
called the Ramsey number Rcr (n). So Ramsey’s Theorem asserts that Rcr (n)
exists, i.e., is finite, for all n, r, c. However, the upper bounds on Rcr (n) are
enormous. For example, a first greedy approach provides a bound that goes up
by the Ackermann hierarchy. Of course better upper bounds are known, such
as s
R2r (n) ≤ 2(r−1)+1 where s = R2r−1 (n − 1) + 1,
which was proven by Erdős and Rado [ER56]. Note that this is roughly only a
tower of 2’s of height r. Indeed, we cannot hope for much better upper bounds.
From the so-called Stepping-up Lemma of Erdős and Hajnal (see e.g. [GRS80])
it follows that

R2r (n) ≥ tr−2 (Cn ) for some constant Cn depending on n,

where the tower function ti (x) is defined as t1 (x) = x and ti+1 (x) = 2ti (x) for i ≥
2. For further results on Ramsey numbers and a good introduction into Ramsey
theory we refer to the book of Graham, Rothschild and Spencer [GRS80].
Finally, let us prove the Erdős-Szekeres Theorem (Theorem 4.12). Indeed
we present three proofs, the first two are based on Ramsey numbers and thus
give very huge bounds on N , the third is an induction that is making more use
of geometry. For convenience let us repeat the statement.
Theorem 4.12 (Erdős-Szekeres Theorem [ES35]).
For every k ∈ N there exists N ∈ N such that every set of n ≥ N points in the
plane in general position contains a convex k-gon.
First proof using Ramsey’s Theorem.
The case k ≤ 3 is immediate and the case k = 4 is covered by Lemma 4.2.
So let k ≥ 5 and X be any set of N points in the plane in general position.
4
We consider X as the vertex set of KN . We define a 2-coloring of the edges of
4
KN by coloring a quadruple red if the four points are in convex position and
blue otherwise. By Ramsey’s Theorem (Theorem 4.13) if N ≥ R24 (k) then there
exists a set Y ⊆ X of k points for which all quadruples contained in Y have the
same color c.
Note that Lemma 4.2 together with |Y | = k implies that this color c can
not be blue, because every set of 5 or more points contains a convex quadruple.
Thus every quadruple of points in Y is in convex position. If Y would not be
convex independent, then by Carathéodory’s Theorem (Theorem 4.1) there is a
point of Y in the convex hull of three other points of Y . Since this would be a
quadruple in non-convex position, we conclude that Y is a convex k-gon.
Second proof using Ramsey’s Theorem.
Let X be any set of N points in the plane in general position. We number the
points in X by x1 , . . . , xN in any order. Now we consider X to be the vertex

52
 3
set of KN and color a triple {xi , xj , xk } with i < j < k red if going from xi to
xj via xk is a left turn and blue if it is a right turn.
By Ramsey’s Theorem (Theorem 4.13) if N ≥ R23 (k) then there exists a set
Y ⊆ X of k points for which all triples contained in Y have the same color c,
without loss of generality red. Again by Carathéodory’s Theorem (Theorem 4.1)
if Y is not a convex k-gon there is a quadruple of points in Y in non-convex
position.

2 2 3 3

4 3 2 1
3 1 4 1 4 1 4 2

Figure 43: Any numbering of four points in non-convex position with distinct
numbers gives at least one left turn i → j → k with i < j < k and one right
turn i → j → k with i < j < k.

But it is impossible to number such a quadruple such that all triples are left
turns. See Figure 43 for a complete case distinction. Thus, Y is a convex k-gon
as desired.
Third proof using induction.
Let X be any set of N points in the plane in general position. First, let us
rotate the plane so that no two points in X have the same x-coordinate. Then
the points of every subset Y of X can be connected by segments from left to
right such that the union of these segments is the graph of some piecewise linear
function. We call a set Y of size k a k-cup if this function is a convex function,
i.e., going through the points in Y from left to right we do only left turns, and a
k-cap if the function is concave, i.e., we do only right turns when walking along
the function graph left-to-right. See Figure 44 for an illustrative example.

Figure 44: A set of 19 points in the plane, a 5-cup in red and a 6-cap in blue.

Clearly, each k-cup and each k-cap is a convex k-gon. Hence it suffices to
prove that if N is large enough then X contains some k-cup or k-cap. We define
f (k, `) to be the smallest number N such that every set of N points in the plane
in general position contains a k-cup or an `-cap.

53
Lemma 4.3. For every k, ` ∈ N we have
 
k+`−4
f (k, `) ≤ + 1.
k−2

Proof of Lemma 4.3. We proceed by induction on k and `. For k ≤ 2 or ` ≤ 2

the statement

clearly holds. Thus let k, l ≥ 3 and consider
any set X of
N =
k+`−4
k−2 + 1 points in general position. Thus N = (k−1)+`−4
(k−1)−2
+ k+(`−1)−4
k−2 + 1,
which by induction hypothesis gives

N ≥ f (k − 1, `) + f (k, ` − 1) − 1.

Suppose that X contains no `-cap. Let A ⊂ X be the set of those points that are
a rightmost point of some (k − 1)-cup in X. Since X \ A contains no (k − 1)-cup
and no `-cap we have |X \ A| < f (k − 1, `) and hence

|A| ≥ N − f (k − 1, `) + 1 = f (k, ` − 1).

Thus A contains a k-cup, in which case we are done, or an (` − 1)-cap Y , each

point of which is a rightmost point of some (k − 1)-cup in X. In particular,
there is a (k − 1)-cup Z whose rightmost point is the leftmost point p of Y . The
situation is depicted in Figure 45.
y y
p
Y Y
p Z z
Z
z

Figure 45: Gluing a (k − 1)-cup Z and an (` − 1)-cap Y necessarily gives a k-cup

(left case) or an `-cap (right case).

Now we look at the predecessor z of p in Z, p itself, and the successor y of p

in Y . Going from z to y via p is either a left turn or a right turn. In the former
case Z ∪ y is a k-cup and in the latter case Y ∪ z is an `-cap, which proves the
lemma.
From Lemma 4.3 immediately follows that if N ≥ f (k, k) then the N -element
point set X contains a convex k-gon, which proves the Erdős-Szekeres Theorem.

Problem 23.
Prove a d-dimensional Erdős-Szekeres Theorem, i.e., that for all natural
numbers k and d there exists N ∈ N such that every set of N points in Rd
in general position (no d + 1 points lie on a common (d − 1)-dimensional
hyperplane) contains k points in convex position.

54
 Of the three proofs

given above the last one implies the best bound on N ,
namely N ≤ 2k−4 k−2 + 1. Even though the proof of Erdős-Szekeres from 1935
gives something stronger then a convex k-gon, namely a k-cup or k-cap, the
derived bound on N was only recently improved by Tóth and Valtr in 1998 and
only by roughly a factor of 2 [TV98].
More precisely, let us define ES(k) to be the minimum n such that every
set of n points in the plane in general position contains a convex k-gon. Equiv-
alently, ES(k) − 1 is the maximum size of a point set in the plane in general
position without any convex k-gon. Then it is known that
 
k−2 2k − 5
2 + 1 ≤ ES(k) ≤ + 2.
k−2

The upper bound is due to Tóth and Valtr [TV98] and the lower bound is a
construction due to Erdős and Szekeres [ES60]. The so-called “Happy Ending
Problem” (named so because it led to the marriage of George Szekeres and
Esther Klein) asks whether the lower bound is the actual truth as conjectured
in [ES35] and confirmed for k = 2, 3, 4, 5, 6.
Before we come to the next problem, recall that f (k, `) denotes the minimum
n such that every set of n points in the plane in general position contain
a k-
cup or an `-cap. In Lemma 4.3 we have shown that f (k, `) ≤ k+`−4 k−2 + 1.
Interestingly, this bound on f (k, `) is tight.
Proposition 4.2. For all natural numbers k, ` ≥ 1 there exists a set Xk,` of
k+`−4


k−2 points in the plane in general position with no k-cup and no `-cap.
Proof. We construct the set Xk,` by induction on k and `. For k ≤ 2 or ` ≤ 2 we
define Xk,` to be a single point. Having defined Xk,`−1 and Xk−1,` we simply
place these two sets suitably next to each other. More precisely, we place Xk,`−1
anywhere and Xk−1,` to the left of Xk,`−1 so that
• Xk−1,` lies completely below all connecting lines of Xk,`−1 of positive
slope, and
• Xk,`−1 lies completely above all connecting lines of Xk−1,` of positive
slope.
We refer to Figure 46 for an example.

Xk,`−1

Xk−1,`

X2,2 X3,3 X3,4 X4,4 Xk,`

Figure 46: Putting a set Xk,`−1 with no k-cup and no (` − 1)-cap next to a set
Xk−1,` with no (k − 1)-cup and no `-cap so as to obtain a set Xk,` with no k-cup
and no `-cap.

By construction each cup Z in Xk,` is either completely contained in Xk,`−1

or contains at most one point of Xk,`−1 . By induction hypothesis we have in the

55
former case |Z| < k and in the latter case |Z| < k − 1 + 1 = k. In other words,
Xk,` contains no k-cup. Symmetrically, every cap Y in Xk,` is either completely
contained in Xk−1,` or contains at most one point of Xk−1,` and we get by
induction hypothesis that |Y | < ` in the former case and |Y | < ` − 1 + 1 = ` in
the latter case. In particular Xk,` contains no `-cap, which proves the claim.

4.5 Empty Convex Independent Subsets

In the preceding section we have been looking for large convex independent
subsets in any big enough set X of points in the plane. Here we consider a very
prominent variant of this problem. Namely, what if we look for large convex
independent subsets in X whose convex hull does not contain any other point
of X? Let us call a subset Y of k points from X a k-hole of X if it is a convex
independent set with conv(Y ) ∩ X = Y . See Figure 47 for some examples. Then
the following question is immediate.

“Does every sufficiently large finite point set in the plane contain a hole of
prescribed size?”

Figure 47: A 3-hole on the left, a 5-hole on the right, and a convex 4-gon that
is no 4-hole in the middle.

Recall that Lemma 4.2 asserts that every set of five points in the plane
contains a convex quadruple. Indeed, by looking at Figure 41 and choosing a
different convex 4-gon the middle case, we see that every such set even contains
a 4-hole.
So let us prove that 5-holes always exist in X, as long as X contains suffi-
ciently many points.
Proposition 4.3. Every set of ES(6) = 17 points in the plane in the general
position contains a 5-hole.
Proof. Per definitionem every set X of ES(6) points in the plane in general
position contains a convex 6-gon Y ⊂ X. Let us refer to the interior of conv(Y )
as simply the interior of Y . We proceed by distinguishing three cases.

Case 1 – (The interior of Y contains at most one point from X.) If there is
no such point then any 5-element subset of Y is a 5-hole. If there is a
point p ∈ X in the interior of Y , then consider any point q ∈ Y and the
line ` connecting p and q. Clearly on one side of ` there is at least three
points of Y . together with p and q these three points form a 5-hole. See
Figure 48(a) for an illustrating example.

Case 2 – (The connecting line of two points of X in the interior of Y leaves

four or more points of Y on one side.) Let p and q be the two points of
X and ` their connecting line. Taking p, q and four points of Y from the

56
 same side of ` gives another convex 6-gon with area smaller than conv(Y ).
Hence repeating this step (or starting with a convex 6-gon of minimal
area) we can reduce the problem to the other two cases. See Figure 48(b)
for an illustrating example.
Case 3 – (The connecting line of any two points of X in the interior of Y
bisects Y .) Consider the convex hull C of all the points of X in the
interior of Y . Let p and q be two consecutive points on C and ` be their
connecting line. Then one side of ` contains three points of Y and no
point of X in the interior of Y . Together with p and q these three points
form a 5-hole, as illustrated in Figure 48(c).

` ` Y
p
p C
Z
q Z Z q
p Y
Y
q
`
(a) (b) (c)

Figure 48: (a) A convex 6-gon Y with exactly one point p inside gives rise to a
5-hole Z. (b) If a convex 6-gon Y is not split evenly by the line connecting ` of
two points p and q inside Y , then this gives rise to a convex 6-gon Z of smaller
area. (c) If a convex 6-gon Y is split evenly by any line ` of any two points in
the interior of Y , then this gives rise to a 5-hole Z.

Since the above is a complete case distinction and in each case we have
identified a 5-hole or a convex 6-gon of smaller area, the statement is proven.
Although not difficult, the proof of Proposition 4.3 is significantly more
involved then for example the proof of Lemma 4.2, which asserts that every set
of five points in the plane in general position contains a 4-hole. One might think
that it is even harder to answer our question above, i.e., whether we always find
a k-hole in any set of n points in general position provided n is big enough.
Indeed, let us do one more step and consider the question whether any n-
element point set, for large n, contains a 6-hole. Apparently this has been
asked by Erdős in 1978 [Erd78] and just recently been answered in the affir-
mative by Nicolás [Nic07] and independently by Gerken [Ger08], as well as by
Koshelev [Kos09]. The bound n ≥ ES(9) stated below is due to Koshelev and
up to today best-known.
Theorem 4.14 (Six-Hole Theorem [Nic07, Ger08, Kos09]).
Every set of ES(9) points in general position contains a 6-hole.
Plugging in the best known upper bound on ES(9) we obtain that every
set of at least 463 points in the plane contains a 6-hole. On the other hand
Figure 49 shows a set of 29 points with no 6-hole, which was found by a computer
search [Ove02]. The exact minimum number of points that always enforce a 6-
hole is not known.

57
Figure 49: A set of 29 points with no 6-hole. This example is due to Over-
mars [Ove02].

We do not present a full proof of Theorem 4.14 here. But all known proofs
proceed as follows.
• Consider any set X of ES(n) points in the plane for some suitable n.
Hence X contains some convex n-gon.
• Take such a convex n-gon C ⊂ X of minimum area.
• Partition C into layers L1 , L2 , L3 , . . . by defining L1 to be the set of corners
of conv(C) and for i > 1 define Li to be the set of corners of conv(C \
(L1 ∪ · · · ∪ Li−1 )). See Figure 50 for an example.
• Prove Lemma 4.4 below.
Lemma 4.4. If X has no 6-hole and |C| ≥ 7, then L4 = ∅.

C = L1
L2

L4 L3

Figure 50: Partitioning conv(C) ∩ X into layers L1 , L2 , . . . by iteratively taking

the convex hull.

Proof that Theorem 4.14 is implied by Lemma 4.4.

By Lemma 4.4 we shall assume that L4 = ∅ and there is no 6-hole, and conclude
that |C| is bounded above by 215. Hence any set of ES(216) points necessarily
contains a 6-hole. Slightly more careful analysis leads to better bounds on |C|.

58
 So if L4 = ∅ and there is no 6-hole then clearly |L3 | ≤ 5. Moreover, the
convex hull of every 6 consecutive points on L2 contains some point of L3 , since
otherwise they would form a 6-hole. Thus |L2 | ≤ 6|L3 | + 5 ≤ 35. Similarly, the
convex hull of every 6 consecutive points of L1 = C contains some point of L2
and thus |C| ≤ 6|L2 | + 5 ≤ 215.
Let us finally answer the initial question of this section, namely whether for
every k there exists an n such that every set of n points in general position
contains a k-hole. We have seen that for k = 3, 4, 5, 6 the answer is ’YES’.
However, for k ≥ 7 the answer is ’NO’ as noted first by Horton already in
1983 [Hor83].
Theorem 4.15 (Seven-Hole Theorem [Hor83]).
There exist arbitrarily large finite sets in the plane in general position with no
7-hole.

The construction presented here is due to Valtr [Val92] and somehow similar
to the one in Proposition 4.2. Indeed we start with a set with only one point
and then define larger sets as the disjoint union of two previously defined sets
A and B with a suitable choice of the relative position of the two sets to each
other.

Definition 4.6. A set H is a Horton set if |H| ≤ 1 or H is the disjoint union of

˙
two Horton sets A and B, i.e., H = A∪B, satisfying conditions (i)–(iv) below.
˙ are equidistant with respect to their x-coordinates.
(i) The points in H = A∪B
(ii) With increasing x-coordinates the points in A and B alternate.

(iii) Every line connecting two points in A lies completely above B.

(iv) Every line connecting two points in B lies completely below A.
Note that (ii) implies that |A| and |B| differ by at most 1.
Lemma 4.5. For every n ≥ 1, there exists a Horton set H on exactly n points.

Proof. One easily sees that if H is a Horton set on n points, then removing the
k points with largest x-coordinate from H gives a Horton set on n − k points
for every k = 0, 1, . . . , n − 1. Hence it suffices to prove the existence of a Horton
set H (k) on 2k points for every k ∈ N.
We start by defining the set H (0) to consist of just one point. Then we
shall define the set H (k) for k ≥ 1 as the disjoint union of two copies A, B of
H (k−1) . We scale A and B so that in either set the x-coordinates of any two
consecutive points differ by exactly 2. Then we place A arbitrarily and B so
that the leftmost point of B lies one unit to the lefts of the leftmost point of
A. This ensures that (i) and (ii) holds for H (k) . Moreover, we place B very far
below A so that also (iii) and (iv) hold.
We refer to Figure 51 for some illustrating examples.
Proof of Seven-Hole Theorem (Theorem 4.15).
We shall show that no Horton set contains a 7-hole. To this end we first show
that for every 4-cup C in a Horton set H there is a fifth point p ∈ H \ C whose
x-coordinate lies between the leftmost and rightmost point in C.

59
 A

B
H (0) H (1) H (2) H (3) H (4)

Figure 51: Horton sets H (k) on 2k points for k = 0, 1, 2, 3, 4.

So let C be any 4-cup in the Horton set H. We write H as H = A∪B ˙ for

Horton sets A and B and may assume without loss of generality that C ∩ A 6= ∅
and C ∩ B 6= ∅. Otherwise, if C ⊂ A or C ⊂ B, we consider the Horton set
A, respectively B, find the desired point p in there and conclude that p is also
good for H.
Now note that (iii) means that the upper half-space of any two points in
A is disjoint from B, see Figure 52(a). This implies that going through C in
left-to-right order we do not see the patterns B − A − B and A − A. Hence at
least one pair of two consecutive points on C is contained in B. But then it
follows from (ii) that between these two points from B there is a point p from
A, as desired. We refer to Figure 52(b) for an illustration.

p
A A A

S
C

p
B B B
H H H
(a) (b) (c)

Figure 52: (a) By (iii) any two points in A define a half-space disjoint from
B. (b) A 4-cup C and a point p ∈ H \ C with x-coordinate strictly between
the leftmost and rightmost point in C. (c) A convex 7-gon S in a Horton set
H = A∪B ˙ and a point p ∈ H inside S.

Analogous arguments show that for every 4-cap C in a Horton set H there
is a point p ∈ H \ C whose x-coordinate is strictly between the leftmost and
rightmost point of C.
Finally assume that H = A∪B ˙ contains some 7-hole S. Again we may
assume without loss of generality that S * A and S * B. Since |S| = 7 either
A or B contains at least four points of S, say B. Because A is far above B,
S ∩ B is a cup of size at least 4. But for every 4-cup C in the Horton set B there
is a point p ∈ B \ C whose x-coordinate is between the leftmost and rightmost
point in C. That this point p is not inside the hole S means that either the
line connecting p with the leftmost or the rightmost point of C cuts through A.

60
This is a contradiction to (iv) and hence no such 7-hole may exist.

Let us summarize the results presented in this and the preceding section with
the following table. We refer to Figure 53 for a set of 9 points in general position
not containing any 5-hole.

k 3 4 5 6 ≥7
k−2
# points enforcing ≥ 2
+ 1
3 5 9 17
a convex k-gon ≤ 2k−5
k−2 + 2

# points enforcing ≥ 30
3 5 10 ∞
a k-hole ≤ 463

Figure 53: A set of 9 points in the plane in general position with no 5-hole.

61
5 Coloring Problems
In this chapter we consider coloring problems that arise from geometric settings
in the plane. All the coloring problems we consider here fit into the following
framework.
Definition 5.1 (The (c, k)-Coloring Problem).
We are given a finite set X, a family F of subsets of X and two natural numbers
c and k. We want to color the elements of X with c colors so that every subset
Y ∈ F contains points of at least k different colors.
For us a c-coloring of X is a mapping φ : X → [c], so the color of some
element x ∈ X is the number φ(x). We then call a c-coloring of X k-good with
respect to F, or simply k-good if F is clear from the context, if

|φ(Y )| ≥ k for every Y ∈ F.

Hence the (c, k)-coloring problem asks for a k-good c-coloring of X with
respect to F.
Let us refer to Figure 54 for an example.

Figure 54: A 2-good 3-coloring of a set of 19 elements with respect to a family

of 20 sets, each of cardinality three.

Problem 24.
Determine all pairs (c, k) for which the example in Figure 54 admits a k-
good c-coloring.

Everybody is probably familiar with the proper graph coloring problem in

which one wants to color the vertices of a graph such that any two vertices that
are joint by an edge receive distinct colors. Of course, assigning every color at
most once gives a proper coloring. So the problem becomes only interesting if
we restrict ourselves to make use of at most c different colors. Translated into
our framework, a proper coloring is just a 2-good coloring of X with respect to
F, where X denotes the vertex set of the graph and F its edge set, and the
proper c-coloring problem for graphs is nothing other than the (c, 2)-coloring
problem.
As already mentioned at the end of Chapter 2 the chromatic number of a
graph is the minimum c for which there exists a proper c-coloring of that graph.

62
Of course, the tuple (X, F) can be seen as the vertex set and edge set of some
hypergraph. And sometimes we refer to it as a hypergraph, but sometimes do
not when it appears to be misleading in the current setting. There is many ways
to define a chromatic number of a hypergraph. We use the following one.
Definition 5.2 (k-Chromatic Number of (X, F)).
The k-chromatic number of (X, F) is denoted by χk (X, F) and defined as the
minimum c for which there exists a k-good c-coloring of X with respect to F.
Note that if (X, F) is a graph, i.e., every set in F has size two, then the
2-chromatic number of (X, F) is just the ordinary chromatic number of that
graph.
Let us further define a special hypergraph which appears frequently in the
literature. It is defined based on any rooted tree T , i.e., a tree with a distin-
guished vertex v0 called the root of T . For any vertex v in T the neighbors of v
at larger distance to v0 than v are called the children of v.
Definition 5.3. For any rooted tree T the hypergraph H(T ) has vertex set V (T )
and edge set F(T ) with Y ∈ F(T ) if and only if
• Y is the set of children of some vertex
• or Y is the set of vertices on a path from the root to a leaf.
An example of the hypergraph H(T ) defined on bases of a rooted tree T is
provided in Figure 55.
v0

Figure 55: A rooted tree T in red with root v0 and the hypergraph H(T ). Edges
corresponding to sets of siblings are highlighted in gray, those corresponding to
path from the root to some leaf are striped.

A rooted tree of particular interest is the full rooted m-ary tree Tm of depth
m − 1. That is, Tm has a root v0 , every vertex v at distance at most m − 2
from v0 (counted by number of edges) has exactly m children, and every vertex
at distance m − 1 is a leaf of Tm . We remark that 2-ary and 3-ary trees are
also called binary trees and ternary trees, respectively. Note that often a rooted
m-ary tree is called full if the root has degree m and all other vertices have
degree either m + 1 or 1. However, we additionally require here that all leaves
have the same distance to the root. Figure 56 depicts T4 , the full rooted 4-ary
tree of depth 4.
Lemma 5.1. For every rooted tree T we have χ2 (H(T )) ∈ {3, ∞}.

63
 ?

Figure 56: The full rooted 4-ary tree T4 of depth 4 with the root in the center.
The hypergraph H(T4 ) that is defined based on T4 consists of all the sets (hy-
peredges) indicated in light gray, as well as all the 44−1 = 64 sets corresponding
to a path between the root and some leaf. One such set is highlighted in dark
gray.

Proof. Let T be any rooted tree. Note that if some non-leaf vertex of T has only
one child, then there is no 2-good coloring of H(T ) and hence χ2 (H(T )) = ∞.
So, for the remainder of this proof we assume that T is a fixed rooted tree and
every non-leaf vertex of T has at least two children.
First we define a 2-good 3-coloring of H = H(T ). To this end color the
vertex of H corresponding to the root of T in color 1 and the remaining vertices
of H with colors 2 and 3 so that no set of children is monochromatic. Clearly
this 3-coloring of H is 2-good, and hence χ2 (H) ≤ 3.
To prove χ2 (H) ≥ 3, we assume for the sake of contradiction that H has
a 2-good 2-coloring φ. Considering any non-leaf vertex v we note that not all
children of v have the same color. Since there is only two colors, there is some
child of v of color φ(v). Hence we can start at the root v0 and make our way
towards some leaf by always going to the child of color φ(v0 ). But then for the
corresponding hyperedge Y we have

|φ−1 (Y )| = |{φ(v0 )}| = 1,

a contradiction to the 2-goodness of φ. We refer again to Figure 56 for an

illustration.

64
5.1 Coloring Points with respect to Ranges
We are particularly interested in hypergraphs that arise from geometric settings,
i.e., are defined geometrically. The examples presented in this section consist of
a finite set X of points in the plane and a possibly infinite collection of subsets
of the plane, so-called ranges. The ranges we consider here are lines, strips and
wedges.
Any given point set X and any collection of ranges defines a family F of
subsets of X by

Y ∈F if and only if ∃range R : Y = R ∩ X.

When a range R gives rise to a set Y ⊆ X by Y = X ∩ R, then we sometimes

say that R captures the points in Y . We start by investigating the following
question.

“For which ranges does the tuple (X, F) have small 2-chromatic number?”

Let us fix any finite point set X and consider lines in the plane as ranges. Of
course we cannot consider all lines in the plane, since many lines would contain
only one point from X and hence give rise to 1-element sets in F, which rules
out the existence of any 2-good coloring.
Hence we restrict only to certain lines, for example all connecting lines of
X. Recall that a line ` is a connecting line of X if |` ∩ X| ≥ 2. Hence in this
case the family F of subsets of X is defined by

Y ∈F if and only if Y = ` ∩ X for some line ` with |` ∩ X| ≥ 2.

Now we are interested in the 2-chromatic number of the the tuple (X, F) ob-
tained this way. That is, we want to color the points in X with as few colors
as possible so that every connecting line contains points of at least two distinct
colors. Clearly, if all points in X are collinear then two colors suffice. Thus
we have χ2 (X, F) = 2 if X is collinear, but it turns out that χ2 (X, F) ≥ 3
otherwise.
Theorem 5.1 (2-Colored Sylvester-Gallai Theorem). For every finite non-
collinear 2-colored set of points in the plane there is a connecting line containing
only points of the same color.
Recall that the Sylvester-Gallai Theorem (Theorem 1.1) states that for every
finite non-collinear set of points in the plane there is a connecting line containing
exactly two of these points, called an ordinary line. Theorem 5.1 is often called
the 2-colored variant of the Sylvester-Gallai Theorem, probably because it guar-
antees the existence of a special connecting line in every (2-colored) finite point
set, unless all points are collinear. However, Theorem 5.1 does not imply the
original Sylvester-Gallai Theorem, and statements of 2-colored point sets that
might be considered as natural strengthening of Sylvester-Gallai’s Theorem are
simply false.

Problem 25.
Construct a finite non-collinear 2-colored set of points for which

65
 a) every ordinary line contains a point from either color.
b) every ordinary line contains two points of the same color.

Anyways, Theorem 5.1 is due to Motzkin [Mot67] and has a beautiful proof
that reminds very much of Kelly’s proof for Theorem 1.1.

Proof of Theorem 5.1.

Let X be a finite 2-colored set of points, not all on a line. Say some points
are colored red and some blue. We consider X and all its connecting lines as
a configuration C in the real projective plane RP2 . Then by Theorem 1.4 the
dual C ∗ of this configuration is a set of lines and points in RP2 , one line for each
point in X and one point for each connecting line of X, such that a point is on
a line in C if and only if the corresponding line contains the corresponding point
in C ∗ .
The 2-coloring of X transfers into a 2-coloring of the lines in the dual. We
now have to prove that there is a point in the dual for which all lines containing
this point have the same color.
If every point is contained in only two lines, i.e., no three lines meet in a
point, then the intersection of any two lines of the same color (which exists since
there are at least three lines) is a point we seek.
So let p be any point which lies on at least three lines, not all of which have
the same color. Consider three lines at p, without loss of generality two red
lines and one blue line. Since not all lines are concurrent there is another line
not containing p. We choose such a line ` which is blue. Indeed, if there is only
red lines not containing p then the intersection of any such red line with a red
line through p is a point we seek.
So ` is a blue line not containing p. We denote the intersections of ` with
the two red lines at p by q1 and q2 , and the intersection of ` with the blue line
at p by p0 . We refer to Figure 57 for an illustration.

p
`
q1 q2
p0
`0

Figure 57: The situation in the proof of the 2-colored Sylvester-Gallai Theorem
(Theorem 5.1).

The triangle pq1 q2 is bounded by three lines, one of color i and the other
two of color j (i 6= j). Moreover there is a third line that A) has color i, B) is
concurrent with the two lines of color j, and C) intersects the side of the triangle
of color i. Now if p0 is not a point we seek, there is a red line `0 containing p0 and
one of the triangles pp0 q1 or pp0 q2 has all the properties mentioned for pq1 q2 ,
but strictly smaller area than pq1 q2 . Hence iterating this process (or starting

66
with a minimum triangle with these properties) finally leads to a point which is
contained only in lines of the same color.
If F is the family of subsets of X captured by some connecting line of
X, then Theorem 5.1 states that χ2 (X, F) ≥ 3, unless all points in X are
collinear. Clearly, if |X| ≥ 2 and all points are collinear, then χ2 (X, F) = 2.
And considering a set X of n points in general position, we easily see that (X, F)
is the complete graph on n vertices and hence χ2 (X, F) = χ(Kn ) = n.

Problem 26.
Prove that if X is any finite point set in the plane and Z is a maximal
subset of X in general position, i.e., no three points of Z are on a line, then

χ2 (X, F) ≤ |Z|,

where F is the family of subsets of X captured by some connecting line of

X. Moreover, find for every m and every n ≥ m + 1 an n-element point set
X whose maximum subset Z of points in general position has size m and
for which χ2 (X, F) < |Z|.

One might think that it is impossible to 2-color a set X of non-collinear

points such that all connecting lines contain both colors, because there are
many ordinary lines, i.e., lines containing only two points from X. This intuition
makes us consider only a subset of connecting lines as ranges. While a connecting
line of X is a line ` satisfying |` ∩ X| ≥ 2, recall from Chapter 2 that for a fixed
number m a line ` is called m-big if it contains at least m points from X, i.e.,
|` ∩ X| ≥ m. We then want to answer the following question.

“Can one 2-color every finite point set X so that every m-big line of X
contains points of either color?”

Clearly, taking m > |X| every 2-coloring will work. But can we find one
number m that works for all sets X? Theorem 5.1 tells us that every set X of
non-collinear points requires m ≥ 3. And for some sets m = 3 is already enough.
For example, Figure 58 shows a finite point set with a 2-good 2-coloring with
respect to its 3-big lines.
Before we answer the question above, let us introduce the m-big idea for
general ranges.
Definition 5.4. For a finite point set X and a natural number m, a range R
is called m-big if |X ∩ R| ≥ m. The family of subsets of X captured by m-big
ranges is denoted by Fm .
Clearly, for every point set X, every type of ranges and for all m ≥ m0 we
have Fm ⊆ Fm0 and hence

for all k and all m ≥ m0 : χk (X, Fm ) ≤ χk (X, Fm0 ).

The question above can now be rephrased and simply asks whether there
exists some m so that every finite point set X admits a 2-good 2-coloring with
respect to m-big lines, i.e., whether χ2 (X, Fm ) ≤ 2. However, as proven by
Pach, Tardos and Tóth in 2007 [PTT07] this is not the case.

67
Figure 58: A set of 9 points with a 2-good 2-coloring with respect to its 3-big
lines.

Theorem 5.2. For every natural numbers m and c there exists a finite point
set X with χ2 (X, Fm ) > c, where Fm denotes the set of all connecting lines of
X containing at least m points of X.
Since we need it in the proof of Theorem 5.2, and because it is interesting in
d
its own right, we state the Hales-Jewett Theorem first [HJ63]. Let Hm denote
the set of integer points of the d-dimensional cube of side length m, i.e.,
d
Hm = {(x1 , . . . , xd ) | xi ∈ {1, . . . , m} ∀i = 1, . . . , d}.
d
A subset ` of Hm is called a combinatorial line if there exists a non-empty set
∅=
6 I ⊆ {1, . . . , d} and a number yi ∈ {1, . . . , m} for every i ∈
/ I such that
` = {xα | α = 1, . . . , m}, where
(
α yi if i ∈ /I
xi =
α if i ∈ I
d
It is easily seen that every combinatorial line of Hm is a m-element subset
of Hm that is captured by some line in R . (Note that no line captures more
d d
d
than m points.) However, not every m-element subset of Hm that is captured
by a line in R is a combinatorial line. See Figure 59 for an example.
d

Theorem 5.3 (Hales-Jewett Theorem).

For every natural numbers m and c there exists a number d such that every
d
c-coloring of Hm contains a monochromatic combinatorial line.
The Hales-Jewett Theorem is considered to be the most applicable theorem
from Ramsey theory. It implies several classic theorems from this area, such as
Van der Waerden’s Theorem [vdW27] and Gallai-Witt Theorem [Rad45, Wit52].
d
Proof of Theorem 5.2. Let m and c be fixed. We consider Hm with the d guar-
anteed by the Hales-Jewett Theorem. Further we consider all m-big lines of
Hm d
, i.e., the set Lm of all lines in Rd containing m points from Hm d
. Clearly,
Lm is a strict superset of the set of lines in R capturing some combinatorial
d
d
line of Hm . Now by the Hales-Jewett Theorem (Theorem 5.3) every c-coloring
d
φ of Hm contains a monochromatic combinatorial line, i.e.,
d
|φ(Y )| = 1 for some ` ∈ Lm with Y = Hm ∩ `.

68
 `3

`1 ∩ H43 = {(4, 1, α) | α = 1, 2, 3, 4}

`2 ∩ H43 = {(α, 4, α) | α = 1, 2, 3, 4}

`3 ∩ H43 = {(α, α, k − α) | α = 1, 2, 3, 4}

`1
`2

Figure 59: The point set H43 . i.e., the integer points of the 3-dimensional
hypercube with side length 4, and three big lines `1 , `2 , `3 capturing exactly
m = 4 points of H43 . The sets `1 ∩ H43 and `2 ∩ H43 are combinatorial lines, while
the set `3 ∩ H43 is not.

d
In particular, there is no 2-good c-coloring of Hm with respect to the family
of all m-big lines. In order to get a 2-dimensional point set, we simply project
Hmd
onto some 2-dimensional subspace of Rd so that no two points of Hm d
are
mapped to the same point and no new collinearities are created.
Considering finite points sets X and the family Fm of subsets of X captured
by m-big lines, then by Theorem 5.2 there is no upper bound on χ2 (X, Fm ) for
fixed m that is independent of X. Next, let us consider another set of ranges,
namely strips. A strip is a subset of the plane spanned between two parallel
lines. In what follows, we consider open strips only.
So fix a finite point set X, we obtain a family F of subsets of X by
Y ∈F if and only if Y = S ∩ X for some strip S with |S ∩ X| ≥ m.
In particular, our ranges are m-big strips. Recall that Theorem 5.2 asserts that
there is no general upper bound on the 2-chromatic number of a finite point
set X with respect to m-big lines. Of course, every such line can be widened
to a narrow strip and hence there is no bound on the 2-chromatic number with
respect to m-big strips neither. However, let us present another, different proof
for strips.
Definition 5.5. For a class C of ranges, we say that a pair (X, F) of a finite
set X and a family F of subsets of X has a realization with C if there is a
point set P (X) of size |X| and a set of ranges from C such that for every subset
Y ⊆ X we have
Y ∈F if and only if Y = P (X) ∩ R for some range R.
Clearly, if we find a realization of some a hypergraph (X, F) with our class
C of ranges, then the maximum 2-chromatic number of a finite point set with
respect to these ranges is at most χ2 (X, F). In particular, if we find a realization
with C of the hypergraph H(T ) for some rooted tree T , then by Lemma 5.1 not
all finite point sets admit a 2-good 2-coloring with respect to C. This argument
has for example been used by Pach et al. [PTT07] as follows.

69
Theorem 5.4. For every rooted tree T , the hypergraph H(T ) has a realization
with open strips.

Proof. We prove the statement by induction on the number of vertices in the

rooted tree T . If T has only one vertex, the root, then it suffices to define a
one-element point set P (X). This point can clearly be captured by some open
strip.
If T contains at least two vertices, we consider any non-leaf vertex v at
maximum distance to the root. In particular, all children of v are leaves in T .
We remove the children of v from T and apply induction to the tree T 0 obtained
this way. We get a realization of H(T 0 ) with open strips, i.e., a set of |V (T 0 )|
points, one for each vertex in T 0 such that every subset of |V (T 0 )| corresponding
to the set of children of some vertex or the set of vertices on some path from
the root to a leaf can be captured by some open strip.
Let p(v) be the point for vertex v, which is a leaf in T 0 . Consider the open
strip S corresponding to the path from the root v0 to v in T 0 . Thus S captures
some subset of points, including the points for v0 and v. Since S is open we can
slightly rotate it changing the subset of captured points. This way we introduce
as many distinct strips, each a slight rotation of the others, as their are children
at v in T . Then there exists another strip S 0 that intersects all these strips,
does not intersect the intersection of any two strips, and does not contain any
point corresponding to a vertex. We introduce one new point for each child of
v in the intersection of S 0 with the strip we introduced for that vertex.
It is not hard to see that this way we have constructed a realization of H(T )
with open strips.
Corollary 5.1. For every natural number m there exists a finite point set X
with 2-chromatic number at least 3 with respect to open m-big strips.
Proof. Take Tm , the full rooted m-ary tree of depth m − 1 and the hypergraph
H(Tm ). By Theorem 5.4 H(Tm ) has a realization with open strips. Since
every hyperedge of H(Tm ) has size m, H(Tm ) has a realization with open strips
capturing at least m points of X each. Now the result follows from Lemma 5.1,
which asserts that χ2 (H(Tm )) = 3.
After several results asserting the non-existence of some colorings (Theo-
rem 5.1, Theorem 5.2, and Theorem 5.4) let us finally present two cases in
which we can find k-good c-coloring with small c and k for certain classes of m-
big ranges. Here we focus on k-good k-colorings, which are of particular interest
in combinatorial geometry.
In the first case, we consider ranges that are wedges. A wedge with apex p
is a connected component of the plane after the removal of two distinct rays
starting at p. Recently, it has been shown that if we consider wedges with only
two distinct apices as ranges, then for any point set we have χk ((X, Fm )) = k,
provided m ≥ 2k [ACC+ 11].
Theorem 5.5. Every finite set of points admits a k-good k-coloring with respect
to 2k-big wedges with two distinct apices.

Proof. Fix k ≥ 2 and let X be a finite set of n points and p1 , p2 the two apices of
wedges. For i = 1, 2 consider the circular ordering σi of the points in X around

70
 1 3
6 14
3 6
1
13
5 14 1 2
p2 13 3 5
2 4 4
12 12
7 5 2
11
14 p1 10 6
8 11 9 8 7
12 7
13
10 4
9
11 9 8
10
(a) (b)

Figure 60: (a) A set of 14 points in the plane numbered along a circular or-
dering σ1 around a point p1 . A circular ordering σ2 around p2 is given by
(. . . , 1, 3, 6, 5, 2, 7, 4, 8, 9, 10, 11, 12, 13, 14, 1, . . .). (b) Grouping σ1 and σ2 into
blocks of size k = 3 and size 1. Elements in σ1 and σ2 that correspond to the
same point in X are connected.

apex pi . In case two or more points of X lie on the same ray emerging from pi
these points are ordered arbitrarily in σi . See Figure 60(a) for an example.
We group the points in σ1 , as well as in σ2 , into bn/kc groups of k consecutive
points each and n mod k groups of 1 point each, so that in no circular two
1-element groups are consecutive. This is possible, since bn/kc ≥ n mod k
provided n ≥ k 2 . See Figure 60(b) for an example.
Next we consider the 2(bn/kc + n mod k) blocks as vertices of a multigraph
G. For each point p in X we draw an edge between the block in σ1 containing
p and the block in σ2 containing p. Note that this way we may draw several
edges between the same pair of blocks. Since every block consists of either 1
or k points, every vertex in G has degree either 1 or k. Now by Vizing’s Theo-
rem [Viz64] the edges of G can be colored with k colors so that any two edges
that share a vertex receive distinct colors. See Figure 61(a) for the continued
example.
Since edges of G correspond 1-to-1 to points in X we get a k-coloring of X.
Moreover, since every block of size k contains all the k colors and between any
two consecutive k-blocks there is at most one further point, we get that every
set of 2k consecutive points in σ1 , as well as σ2 contain all the k colors. In other
words every wedge with apex p1 or p2 that captures at least 2k points of X
contains at least one point of each color, see Figure 61(b). This concludes the
proof.
Next we consider ranges that are x-monotonously decreasing curves in the
plane, which we call decreasing curves for short. That is, a set Y of points is
captured by some decreasing curve γ if and only if the points in Y have distinct
x-coordinates and going through the points in order of increasing x-coordinates
the y-coordinates are strictly decreasing. See Figure 62 for an illustration. Note
that without loss of generality we can restrict ourselves to continuous decreasing
curves.

71
 6
3
1
5
p2 2 4
7
14 p1
8
13 12
11 10 9

(a) (b)

Figure 61: (a) Blocks are contracted to vertices of a bipartite graph of maximum
degree k = 3, whose edges are colored with k = 3 colors. (b) The coloring is
transferred to the point set X.

Figure 62: A finite point set and two decreasing curves capturing four points
each.

For convenience let us call a subset Y of X that is captured by some decreas-

ing curve a decreasing subset. It is easily seen that every subset of a decreasing
subset is decreasing again. Hence, if a decreasing subset of n points admits a
k-good c-coloring with respect to m-big decreasing curves, then m · c ≥ n · k.
Looking at k-good k-colorings we get m ≥ n. In particular, a first necessary
condition for every set X to have a k-good k-coloring with respect to m-big
decreasing curves is that
(1) every decreasing subset of X has size at most m.

Clearly, if every subset that is captured by a range shall contain at least k

different colors, then every subset should contain at least k elements. Thus
another obviously necessary condition for the existence of any k-good coloring
is that
(2) all ranges are at least m-big with m ≥ k.

With (1) and (2) we have two obviously necessary conditions that need to be
satisfied in order that a finite set X admits a k-good k-coloring with respect to
m-big decreasing curves. Interestingly, these conditions are already sufficient.
Theorem 5.6. Every finite point set X in which every decreasing subset has
size at most m (i.e., (1) is satisfied) admits a k-good k-coloring with respect to
m-big decreasing curves, provided m ≥ k (i.e., (2) is satisfied).

72
Proof. Let k and m ≥ k be fixed. Consider any point set X that satisfies (1).
We shall find a k-good k-coloring of X with respect to its m-big decreasing
curves. Clearly, it is enough to consider the case m = k, since for all m0 ≥ m
we have χk ((X, Fm0 )) ≤ χk ((X, Fm )).
We shall prove the existence of a k-good k-coloring φk of (X, Fk ) for every
point set X satisfying (1) with m = k by induction on k. If k = 1, then (1) we
seek a 1-good 1-coloring, which simply amounts to coloring all the points in X
the same.
So let k ≥ 2. Consider any set Y ∈ Fk , i.e., any decreasing subset of X of
size m = k. No two points in Y have the same x-coordinate and thus there is
a unique rightmost point in Y , i.e., the point with maximum x-coordinate. We
define Z to be the set of all rightmost points of all sets Y ∈ Fk . If we remove Z
from X we get a point set X 0 = X \ Z in which every decreasing subset has size
at most k − 1. Hence by induction there exists a (k − 1)-good (k − 1)-coloring
φk−1 of X 0 . Extending φk−1 to the larger set X by assigning a new k-th color
to all points in Z, we obtain a desired k-good k-coloring φk .

Problem 27.
Let m ≥ 2 and X be a point set in the plane in which all decreasing subsets
have size at most m. Find a finite superset X̄ ⊇ X, such that all decreasing
subsets of X̄ have size at most m and every decreasing set Y ⊆ X is
contained in a decreasing subset of X̄ of size exactly m.

5.2 The Dual Coloring Problem

In the (c, k)-coloring problem considered in Section 5.1 we have colored points
in a finite point set X with respect to ranges of a certain type. In this section we
introduce the dual problem, in which we color a finite set of ranges of a certain
type with respect to points.
We start by defining the dual of a hypergraph H = (X, F). This is a hyper-
graph H ∗ = (X ∗ , F ∗ ) whose vertices are in bijection with the hyperedges of H,
X ∗ ≡ F, and whose hyperedges are in bijection with the vertices of H, F ∗ ≡ X.
More precisely, for every hyperedge Y of H there is a vertex Y in H ∗ , for every
vertex x of H there is a hyperedge x in H ∗ , and Y ∈ X ∗ is contained in x ∈ F ∗
if and only if x ∈ X is contained in Y ∈ F. In other words

Y ∈ x in H ∗ ⇔ x ∈ Y in H.

So when taking the dual H ∗ of a hypergraph H, we just swap the meanings of

vertices and hyperedges and reverse the containment relations. See Figure 63
for an example.
Dualizing a hypergraph is very similar to dualizing an arrangement of points
and lines in projective plane (c.f. Theorem 1.4) where we exchange the meanings
of points and lines. Indeed the dual configuration of a configuration of points and
lines in RP2 obtained in Theorem 1.4 is just a realization of the dual hypergraph
defined by the first configuration. This fact is illustrated in Figure 64.

73
 c
d
c
a
a
b d
f e
b
e f

H H∗

Figure 63: A hypergraph H with 7 vertices and 6 hyperedges and its dual
hypergraph H ∗ with 6 vertices and 7 hyperedges.

Problem 28.
Show that for every rooted tree T the dual hypergraph of H(T ) admits a
realization with open strips.

Now assume the hypergraph H = (X, F) arises from a geometric setting

where X denotes a point set and F the family of subsets of X captured by a
range from a given collection of ranges. Clearly, we can pick for every set Y ∈ F
one representative range R that captures this set Y . For every set Y there could
be infinitely many ranges R that capture Y , but for every two distinct sets Y, Y 0
every representative range for Y is distinct from every representative range for
Y 0 . This way H = (X, F) can be completely described by |X| points and |F|
representative ranges.
Now the dual hypergraph H ∗ of H can be interpreted as follows. The vertices
of H ∗ are the finite set of representative ranges and a subset Y of ranges form
a hyperedge in H ∗ if there is a point x in X that is contained in precisely the
ranges in Y . In this case we say that a set Y of ranges is pierced by the point
x. We can now think of each point in X as a representative point for a set Y
of ranges. Clearly, there can be infinitely many points in the plane that pierce
exactly the set Y . See Figure 65 for some illustration.
In the general dual setting we consider a hypergraph H ∗ whose vertex set is
a finite set of ranges and whose hyperedges are defined with respect to a certain
(most of the times infinite) collection of points in the plane. Analogous to m-big
ranges, we now consider m-deep points.
Definition 5.6. For a finite set X ∗ of ranges and a natural number m, a point
p is called m-deep if |{R ∈ X ∗ | p ∈ R}| ≥ m. The family of subsets of X ∗
∗
pierced by m-deep points in the plane is denoted by Fm .
The dual (c, k)-coloring problem then asks for a k-good c-coloring of a set
X ∗ of ranges with respect to m-deep points. In particular, we want to color the
ranges in X ∗ with c colors such that every set of ranges that is pierced by an
m-deep point contains at least k distinct colors.
For simplicity we refer to the original (c, k)-coloring problem, where the
points are colored with respect to ranges, as the primal problem. While the
(c, k)-coloring problem in which ranges are colored with respect to points is
called the dual problem. The following table summarizes the different notions
in the primal and the dual setting.

74
 configuration of 4 points dual configuration of
and 3 lines in RP2 3 points and 4 lines in RP2
c 1
1 b
b 2 4
c 2
3 a
2
a dualize in RP
4 3

has defines has defines

realization hypergraph realization hypergraph

hypergraph on 4 vertices dual hypergraph on

and 3 hyperedges 3 vertices and 4 hyperedges
b 4
b
1 4 1
a
2 3 a
c dualize in c 2
hypergraphs
3

Figure 64: Dualization of point-line configurations in RP2 is a special case of

hypergraph dualization.

Primal Dual

vertex x ∈ X hyperedge x ∈ F ∗
General
Hypergraphs hyperedge Y ∈ F vertex Y ∈ X ∗

x∈Y Y ∈x

point x ∈ X range R ∈ X ∗
Geometric
Hypergraphs m-big range R m-deep point p

∗
R captures Y ∈ Fm p pierces Y ∈ Fm

(c, k)-Coloring color points in X with color ranges in X ∗

Problem c colors with c colors

such that every R such that every point p

captures k colors pierces k colors

As already mentioned before, we are particularly interested in k-good k-

75
Figure 65: Five points captured by a square and five squares pierced by a point.

colorings of geometric hypergraphs in the primal as well as in the dual setting.

That is, we color the elements (points in the primal problem, ranges in the dual
problem) with k colors so that every set in F, respectively F ∗ , (points captured
by a range in the primal, ranges pierced by a point in the dual) contains elements
of each of the k colors. Such sets are sometimes also called colorful.

Definition 5.7. For a fixed type T of ranges we define

• m(k) to be the minimum m such that every finite point set X in the plane
admits a k-good k-coloring with respect to m-big ranges of type T , and
• m∗ (k) to be the minimum m such that every finite set X ∗ of ranges of type
T admits a k-good k-coloring with respect to m-deep points in the plane.
Given any k-good k-coloring with respect to m-big ranges in the primal
setting or with respect to m-deep points in the dual setting, we can obtain a
(k − 1)-good (k − 1)-coloring with respect to the same m by simply uniting two
colors into one. Thus for every type of ranges the functions m(k) and m∗ (k)
are monotonously non-decreasing in k. Thus if m(k) = ∞ for some k ∈ N then
m(k 0 ) = ∞ for all k 0 ≥ k.
Curiously, we do not know whether there is a type of ranges such that m(2)
is finite but m(k) is infinite for some large k. And the same question is open
in the dual setting, i.e., whether there is a type of ranges such m∗ (2) < ∞ but
m∗ (k) = ∞ for some k. For example, in the next section we discuss a type
of ranges for which was known that m∗ (2) = 3 but open whether m∗ (3) < ∞.
(Today we know for this particular type of ranges that m∗ (k) < ∞ for all k.)
We can derive the following bounds on m(k) and m∗ (k) from our results in
the previous section (Section 5.1).

76
 type of range m(k), m∗ (k) reference

lines m(2) = ∞ Theorem 5.2

∗
lines m (2) = ∞ Theorem 5.2 and
Theorem 1.4

strips m(2) = ∞ Theorem 5.4

∗
strips m (2) = ∞ Problem 28

wedges with two apices m(k) ≤ 2k Theorem 5.5

decreasing curves m(k) = k Theorem 5.6

Remark. It is important to note that the value m(k) = k for decreasing curves
actually holds only if we restrict ourselves to point sets X in which no k + 1
points lie on a decreasing curve.
Before we continue, let us briefly mention the original motivation for the
(c, k)-coloring problem of geometric hypergraphs. In the 1980’s János Pach and
others considered k-fold coverings of the plane with certain type of bodies, such
as unit discs. A k-fold covering is an infinite collection of subsets, all begin
translates of another, such that every point in the plane is covered at least k
times, i.e., is contained in at least k such subsets. (Usually those coverings are
assumed to be locally finite, that is, every point in the plane is contained in
only finitely many subsets.)
To investigate the minimum density of such a k-fold covering, the question
arose whether every k-fold splits into roughly k disjoint coverings, or about k/l
disjoint l-fold coverings for some l < k. Note that the former question simply
asks whether m∗ (k) < ∞ with respect to ranges that are translates of a fixed
set, while the latter asks whether there is a dual l-good k/l-coloring.
In 1986 [Pac86] János Pach showed that if the ranges are translates of a
fixed convex polygon P then m∗ (k) < ∞. However, his bound was doubly-
exponential in k, and has only been improved recently by Pach and Tóth [PT09]
to m∗ (k) ∈ O(k 2 ). Both bounds involve a constant factor cP that depend on the
number of corners of the convex polygon P , which tends to infinity as P tends
to a smooth object. The only “result” for smooth ranges is in an unpublished
manuscript by Mani-Levitska and Pach [MLP87] in which they show that every
33-fold covering with unit discs decomposes into two coverings. However, this
manuscript appears to be lost and the statement has never been verified by
others. The convexity is indeed crucial, since if regions are translates of a fixed
concave quadrilateral, then m∗ (2) = ∞ [PTT07].
The next theorem shows that in all of the above cases that are stated in the
dual version, the same bounds hold also for the primal problem.
Theorem 5.7. If we consider ranges that are translates of a fixed body S in the
plane then we have
m(k) = m∗ (k) for every k ∈ N.

Proof. Let S be a fixed body in the plane and X be any finite point set. We
fix for every set Y ∈ Fm , i.e., any subset Y of X that is captured by some

77
m-big range, one representative range SY with X ∩ SY = Y . Clearly, SY is a
translated copy of S, i.e., there exists some pY ∈ R2 such that

SY = S + pY = {p ∈ R2 | p = s + pY for some s ∈ S}.

The hypergraph H = (X, Fm ) is now given by a finite set X of points and a

finite set S of translates of S, one for each set in Fm , such that a vertex x is
contained in a hyperedge Y if and only if the point x is contained in the range
SY .
Next we shall prove that the dual hypergraph H ∗ = (X ∗ , Fm ∗
) has a realiza-
tion with translates of S, too. To this end, we define for every x ∈ X
def
Sx = x − S = {p ∈ R2 | p = x − s for some s ∈ S}.

That is, Sx is a translated copy of S after a rotation of π. We refer to Figure 66

for an illustration.

SY1 Sx2

pY1 x1 x2 pY1
Sx1
pY2 x3

pY2
SY2 Sx3

Figure 66: Two representative ranges SY1 and SY2 and three points x1 , x2 , x3
are transformed into two points pY1 and pY2 and three representative ranges
Sx1 , Sx2 , Sx3 .

Now we claim that H ∗ = (X ∗ , Fm

∗
) has a representation with translates of
S, which is given by

• X ∗ = {pY | Y ∈ Fm } and
∗
• Fm = {Yx ⊆ X ∗ | Yx = X ∗ ∩ Sx for some x ∈ X}.
Indeed, we have for every Y ∈ Fm and every x ∈ X that

x ∈ Y ⇔ x ∈ SY ⇔ x = pY + s for some s ∈ S
⇔ pY = x − s for some s ∈ S ⇔ pY ∈ Sx ⇔ pY ∈ Yx .

Because both H and H ∗ admit a realization by the same type of ranges, it

follows that the (c, k)-coloring problem for H = (X, Fm ) is equivalent to the
dual (c, k)-coloring problem for H ∗ = (X ∗ , Fm
∗
). In particular, this implies
m(k) = m (k) for every k ∈ N.
∗

All the considerations above involve only translates of regions. But the ”big
question“ of Pach that apparently is open for almost 30 years now concerns
homothetic regions.

78
Question 5.1 (Pach 1986).
Is it true that for every convex polygon P in the plane, if we consider ranges
that are homothetic copies of P , then m∗ (k) < ∞ for every k ∈ N?

If P is smooth, rather than a polygon, then the answer is ’NO’, because for
every tree T the hypergraph H(T ) admits a dual realization with homothetic
discs [PTT07].

5.3 Online Coloring Problems

In this section we present a set of techniques that in recent years proved to
be very useful to bound m(k) and m∗ (k) for several types of ranges: online
colorings.
Actually, every combinatorial optimization problem that given a certain fi-
nite input seeks for a certain solution that maximizes or minimizes a certain
value also has a meaningful online variant. Let us motivate this with a small
example.
Example (The Online Hanging Problem).
When at home the washing machine is finished, the set C of wet clothes needs
to be put onto a laundry rack for drying. The rack has some number j of drying
lines, each of length 1. Each piece of clothing x has a width w(x) and must
be assigned to a consecutive subset of length w(x) of one of the lines so that
distinct pieces of clothing are assigned to disjoint subsets of drying lines. We
refer to Figure 67 for an illustration.

Figure 67: A set C of two pieces of clothes and a laundry rack with j = 4 drying
lines.

Because we might decide for another run of the washing machine, the (of-
fline) hanging problem is now to find a placement for each piece of clothes in C
on the laundry rack such that it occupies the least number of drying lines.
In case my wife and I are both at home we usually share the work load of
hanging out the laundry. Then my wife has the pile C of wet clothes, takes
one piece at a time, unfolds it and hands it over to me. I then take the piece of
clothes x and assign it to a consecutive subset of width w(x) of one of the drying
lines. This lets us finish very quickly. However, in order not to lose much time
we have to obey the following two restrictions.

No forecast. I cannot inspect the pile of clothes yet to come. That is, I neither
know how many clothes nor what kind of clothes are yet to come. I do not
even know whether the current piece of clothes in my hand is the last one.

79
No reconfiguration. I cannot reassign any piece of clothes. As soon as I
decided to place a piece onto a certain subset, this decision is irrevocable.

The problem I am facing now is called the online hanging problem. That is,
I shall assign each piece of clothes once I have it in my hands to some suitable
subset of a line, under the restriction that I have no information about the
clothes yet to come and I may not reconfigure any piece of clothes that already
hangs. And I shall do it in such a way that I use as few lines as possible. Indeed,
I want to minimize the difference between the number of lines I used in the end
and the number of lines that would carry the set C of clothes.
For example, let us consider the following situation. I have j = 2 racks at
my disposal and my wife guarantees me the laundry can fit onto these two lines.
(This is a piece of information that is usually not provided!) Then the following
happens.

1) My wife starts by giving me a T-shirt x1 of width w(x1 ) = 0.4 and I put it

onto the first drying line `1 at the very left. (It is easily seen that placing
pieces of clothes always left-aligned is not disadvantageous.)
2) Then my wife gives me another T-shirt x2 of width w(x2 ) = 0.4 and I can
choose to place it also on `1 or on the second line `2 .
3) I decide to put x2 on `2 . Then my wife gives me a blanket x3 of width
w(x3 ) = 1 and I cannot place it onto the rack, although all three pieces
could fit on it. This is illustrated in Figure 68.

? 0.4

x3 x2

x1

Figure 68: Placing T-shirts x1 and x2 on different drying lines is bad if next
comes a large blanket.

It seems that I should have put x2 also on `1 .

3’) I decide to put x2 also on `1 . Then my wife gives me a sweater x3 of width

w(x3 ) = 0.6 and another sweater x4 of the same width w(x4 ) = 0.6. I can
place only x3 on the rack, although all four pieces could fit on it. This is
illustrated in Figure 69.

Apparently, when my wife and I hang the laundry online, then we are a lot
quicker, but might need a larger laundry rack.

80
 0.6

?
0.4 0.4
x3

x1 x2
x4

Figure 69: Placing T-shirts x1 and x2 on the same drying line is bad if next
comes two medium size sweaters.

Here we want to consider online versions of the (c, k)-coloring problem in-
troduced in Definition 5.1 at the very beginning of this chapter. In particular,
a hypergraph H = (X, F) is presented in rounds (instead of given as input) as
follows.

• In each round exactly one new vertex is presented.

• Every hyperedge Y is presented together with its vertex that is presented
last.

So in each round there is exactly one new vertex, but there could be any
number of new hyperedges, ranging from none to arbitrarily many. In the online
(c, k)-coloring problem we then want to do the following.

(O1) Color every vertex immediately when it appears.

(O2) Use at most c colors.
(O3) Never recolor any vertex.
(O4) Ensure that every hyperedge contains vertices of at least k different colors.

Before we actually define the online (c, k)-coloring problem and the online
k-chromatic number, let us already present a first result due to Gyárfás and
Lehel [GL88]. It states that the online proper coloring problem is basically
hopeless, even for very simple graphs, namely trees.
Theorem 5.8. There is no constant c such that every tree can be properly
colored online with at most c colors.
Proof. We shall define for every c ∈ N an adversarial strategy S(c) that no
matter how vertices are colored eventually produces a tree that contains vertices
of at least c different colors. We remark that we present a strategy and not a
tree. The tree produced by S(c) will depend on the intermediate coloring of
vertices.
We prove the existence of S(c) by induction on c. In the base case c = 1 it
suffices to present a single vertex. So let us assume that c ≥ 2. By induction

81
there exists a strategy S(c − 1) that eventually produces a tree containing at
least c − 1 different colors. We present the strategy S(c − 1) c − 1 times in a row,
which gives us c − 1 trees T1 , . . . , Tc−1 , each containing at least c − 1 different
colors.
Now we distinguish two cases.

Case 1: There are at least c different colors in T1 ∪ . . . ∪ Tc−1 . Then we simply

present one more vertex v with exactly one edge into each Ti for i =
1, . . . , c − 1. This gives a tree T that, independent of the color assigned to
v, contains vertices of at least c different colors.
Case 2: Each Ti contains the same set of c − 1 colors for i = 1, . . . , c − 1.
Without loss of generality the c − 1 colors are 1, . . . , c − 1. Then we choose
for each i ∈ {1, . . . , c − 1} a vertex vi from Ti of color i. We present
one new vertex v with an edge to each vi , i = 1, . . . , c − 1. Clearly, v
must receive a new color and we have forced c colors in total. We refer to
Figure 70 for an illustration.

3
2 2 2 2 2 2 ...
1 1 1 1 1 1 1 1

Figure 70: How the first steps in the adversarial strategy to force arbitrarily
many colors in a tree may look like.

This completes the proof.

Under the light of Theorem 5.8 the usefulness of coloring a (hyper)graph
online may seem questionable. Of course, online problems in general are very
important in practice, e.g., when it comes to assignments of jobs to machines
inside some never-ending mechanism, such as the internet. However, as we shall
see later, at least for geometric hypergraphs online colorings also imply strong
results in the offline settings. And sometimes the best known offline bounds are
actually generated by online considerations.
In the online setting it no longer makes sense to talk about one fixed hyper-
graph and something like its ”online chromatic number“. Because, if it is only
one hypergraph H and admits some k-good c-coloring φ then we could simply
color according to φ. And if H has no k-good c-coloring, then of course pre-
senting H online does not make it better. The idea of online coloring problem
is that we do not know which hypergraph H is going to be presented. All that
we know is that H is a hypergraph from a certain class of hypergraphs, such
as, trees, the hypergraphs H(T ) for any rooted tree T , or the hypergraphs that
admit a realization with points in the plane and subsets of those points captured
by a certain type of ranges.
Note that, while we defined the (offline) (c, k)-coloring problem for one par-
ticular fixed hypergraph, most of our investigations actually also considered a
certain class of hypergraphs.
Let us make this a little more formal.

82
Definition 5.8 (Online (c, k)-coloring problem).
Let C be a class of hypergraphs. An online k-good c-coloring of C is a class Φ of
exactly one k-good c-coloring φ for each H ∈ C and each ordering of the vertices
in H, such that the following is true.
• Whenever the vertex orderings of two hypergraph H, H 0 ∈ C coincide in
the first n positions for some n, then the corresponding colorings φ and φ0
coincide on these first n vertices, too.
The online k-chromatic number of C is then defined as
def
k (C) = min{c ∈ N | there exists an online k-good c-coloring of C}.
χON
With this definition Theorem 5.8 can be conveniently rephrased as
χON
k (T ) = ∞ ∀k ≥ 2,
where T denotes the class of all trees.
Next we consider a different class of hypergraphs and show that its online k-
chromatic number is indeed finite for every k. Let Cm be the class of hypergraphs
that admit a realization with m-big decreasing curves, such that every decreasing
curve captures at most m points. In particular, we consider exactly the class
of hypergraphs from Theorem 5.6, in which we showed that for the case m = k
every such hypergraph H ∈ Cm=k admits a k-good k-coloring, that is χk (H) = k.
It is easy to see that there is no online k-good k-coloring of Ck . Hence we
have to either increase the number of colors, or decrease the level of goodness.
We take the first option and want to find the minimum c for which there exists
an online k-good c-coloring of Ck . In particular, we want to determine χON
k (Ck ).

Theorem 5.9. For every k ≥ 1, every set of points in the plane with
no k + 1
points on a decreasing curve can be colored online with at most k+12 colors such
that every decreasing subset of size k contains k different colors.
Proof. We are presented points in the plane one after

another and we shall color
each point as it appears with one of at most k+1 2 colors, such that whenever
two points are captured by some decreasing curve they receive distinct colors.
So let p be the point that just appeared and is yet to be colored, and X be the
set of points presented so far. We define two auxiliary numbers for p. We say
that a decreasing subset Y starts at s ∈ Y and ends at t ∈ Y if s is the leftmost
point in Y and t is the rightmost point in Y .
def
L(p) = size of the largest decreasing subset in X ∪ p ending at p.
def
R(p) = size of the largest decreasing subset in X ∪ p starting at p.

Now we color the point p with the ordered tuple (L(p), R(p)). Since the
union of any decreasing subset ending at p and any decreasing set starting at
p is a decreasing set again, we conclude that L(p) + R(p) ≤ k + 1. Hence the
total number of colors we use is at most

k
X k+1−L(p)
X k
X k
X  
k+1
1= (k + 1 − L(p)) = L(p) = .
2
L(p)=1 R(p)=1 L(p)=1 L(p)=1

83
 It remains to show that if two points p and q are captured by some decreasing
curve, then these points receive distinct colors. So consider such p and q and
assume without loss of generality that q appeared prior to p. The point q
received the color (L(q), R(q)) with respect to the point set X that was presented
prior to q. Now consider the moment that p is presented and consider the point
set Y that is already presented at this time. Clearly, Y ⊃ X and hence every
decreasing subset in X is also a decreasing subset in Y .
By assumption p and q are on a decreasing curve, that is, p is presented either
to the top-left of q or to the bottom-right of q. In the first case the decreasing
subset R ⊆ X of size R(q) can be extended by p to a decreasing subset of Y of
size at least R(q) + 1 starting at p. In particular we have R(p) ≥ R(q) + 1 and
the colors of p and q are different. Similarly, if p is presented to the bottom-right
of q then the decreasing subset L ⊆ X of size L(q) can be extended by p to a
decreasing subset of Y ending at p. Hence L(p) ≥ L(q) + 1 and the colors of p
and q are not the same.
Using the notation from Definition 5.8 we can state Theorem 5.9 as
 
k+1
χON
k (C k ) ≤ .
2

Next, we show that this upper bound is indeed tight for every k ≥ 1.

Theorem
5.10. For every k ≥ 1 there is no online k-good c-coloring of Ck with

c < k+1
2 . In particular with Theorem 5.9 we have
 
k+1
χON
k (Ck ) = .
2

Proof. For a fixed k we shall provide an adversarial strategy Sk to present points

in the plane with no k + 1 on a decreasing curve such that whenever the points
are colored online so that any decreasing

subset of size k contains k different
colors, then this uses at least k+1 colors. So we fix any online k-good c-coloring
2

Φ of Ck and shall prove that c ≥ k+1 2 .
Claim. Whenever two of the presented points lie on some decreasing curve then
these points are colored differently by Φ.
Proof of Claim. If two such points p and q would get the same color, then
we could simply present more points to complete some decreasing subset Y of
size k containing p and q. (Note that this is always possible without creating
decreasing subsets of size more than k.) Then Y would contain at most k − 1
colors, contradicting the fact that Φ is k-good.
The adversarial strategy Sk consists of certain ”building blocks“. In each
such block we present points in such a way that they satisfy a certain set of
properties, which we call X(i) for some natural number i, no matter how these
are colored with respect to Φ. A point set X is said to have property X(i) for
some i ∈ N if the following holds.

I) The i lowest points p1 , . . . , pi in X (those with smallest y-coordinate) are

all colored differently by Φ and can be captured by an increasing curve.

84
 II) The points in X \ {p1 , . . . , pi } can be captured by a decreasing curve.
Moreover, each point in X \ {p1 , . . . , pi } has the same color as some pj ,
j ∈ {1, . . . , i}.

Note that by the Claim above, all points in X \ {p1 , . . . , pi } are colored
differently and hence from II) it follows that |X| ≤ 2i.
We show that for each i ∈ N we can present a point set that is forced to
have property X(i) by induction on i. For i = 1 it clearly suffices to present
a single point. For i ≥ 2 we first present a point set X that has property
X(i − 1) and denote the i − 1 lowest points of X by p1 , . . . , pi−1 . Then we
present the next point p to the right of all points in X and horizontally between
{p1 , . . . , pi−1 } and X \ {p1 , . . . , pi−1 }, i.e., p is above p1 , . . . , pi−1 and below all
points in X \ {p1 , . . . , pi−1 }. See Figure 71 for an illustration.

31 4 31 4 31 4
p p
6 2
3 5 3 5 3 5
1 2 4 1 2 4 1 2 4

X satisfies X ∪ p satisfies X ∪ p satisfies

property X(i − 1) property X(i) property X(i − 1)

Figure 71: Starting with a point set X with property X(i − 1) (left) we produce
a point set with property X(i) (middle) or a larger point set with property
X(i − 1) (right).

Now p receives a color c by Φ. If c is a new color, that is, a color that is not
present in X so far, then X ∪ p satisfies property X(i) and we are done. See
the middle of Figure 71. Otherwise, if some point in X already has color c then
by II) it must be a color that appears among p1 , . . . , pi−1 . In particular, X ∪ p
has again property X(i − 1) as illustrated in the right of Figure 71. Since every
point set with property X(i − 1) has at most 2(i − 1) points, it follows that at
latest after the (2i − 1)-th point is presented we have a set that has property
X(i).
Finally, we use the building blocks X(i), i ∈ N , to define the adversarial
strategy Sk as follows. We refer to Figure 72 for an illustration.
• Start by presenting a set Xk having property X(k). Denote the set of the
k lowest points in Xk by Lk .

• For i ≥ 1, present a set Xk−i having property X(k − i) to the left of

Xk−i+1 , above Lk−i+1 and below Xk−i+1 \ Lk−i+1 . Denote the set of the
k − i lowest points in Xk−i by Lk−i .
By I) we have that each Li contains exactly i colors. And by the Claim
above these colors are different for different Li . Thus the total number of colors

85
 Lk−3
Lk−2
Lk−1
Lk

Xk−3 Xk−2 Xk−1 Xk

Figure 72: An example point set that could arise from the adversarial strategy
Sk with k = 4.

in X = Xk ∪ Xk−1 ∪ · · · ∪ X1 is
1
X 1
X  
k+1
|Li | = i= .
2
i=k i=k

It remains to show that no k + 1 points of X lie on some decreasing curve.

So let Y be any decreasing subset of X. From the construction follows that if
Y ∩ (Xi \ Li ) 6= ∅ for some i then Y ∩ Xj = ∅ for all j < i and Y ∩ (Xj \ Lj ) = ∅
for all j > i. Moreover, by I) we have that |Y ∩ Lj | ≤ 1 for all j = 1, . . . , k.
Doing the counting we get
k
X
|Y | = |Y ∩ (Xi \ Li )| + |Y ∩ Lj | ≤ (i − 1) + (k − i + 1) = k,
j=i

which concludes the proof.

Next we introduce another type of ranges, which will be the subject of our
investigations for the remainder of this chapter: bottomless rectangles.
A bottomless rectangle is an axis-aligned rectangle in the plane whose bot-
tom edge is at −∞. Given any finite point set X and a natural number m we are
interested in the subsets Y of X captured by some m-big bottomless rectangle.
As usual, the family of those subsets is denoted by Fm . See Figure 73(a) for an
illustrating example.
Let us consider another class of hypergraph which is denoted by Im for some
natural number m and defined as follows. A hypergraph H = (X, F) is in Im (I
stands for interval) if every hyperedge contains exactly m vertices and for each
vertex v in X there exist two real numbers xv and tv such that the following is
true.

Y ∈F ⇐⇒ ∃`, r, t ∈ R such that Y = {v ∈ X | tv ≤ t and ` ≤ xv ≤ r}.

The numbers are interpreted as follows. Every vertex v corresponds to a

point on the real line together with an insertion time tv , i.e., v is an ordered

86
 t = 6.5

1 7 5 9 3 6 10 2 48

(a) (b)

Figure 73: (a) A finite point set X on 10 points in the plane, the (hyper)graph
H = (X, F2 ) and one 2-big bottomless rectangle for each (hyper)edge in H.
(b) The point set X seen as points on the real line with insertion times and a
bottomless rectangle seen as an interval with a time t. The points captured by
the bottomless rectangles and interval at time t are highlighted, respectively.

tuple of two real numbers xv and tv . Time starts at −∞ and increases steadily.
Then the points show up on the initially empty real line one-by-one. Indeed,
the point for v shows up at its insertion time tv and never disappears again. If
at some time t an interval I = [`, r] ⊂ R contains the subset Y of points then
we say that interval I captures the points in Y . Here a point can be captured
only if it already appeared by time t, that is, if its insertion time is at most t.
See Figure 73(b) for an example.
Lemma 5.2. For every m ∈ N every hypergraph H = (X, Fm ) with respect to
m-big bottomless rectangles is a hypergraph in Im and vice versa.
In particular, for all natural numbers m and k and every hypergraph H =
(X, Fm ) with respect to m-big bottomless rectangles we have

χk (H) ≤ χON
k (Im ).

Proof. A bijection σ between the model with points in the plane and bottomless
rectangles and the model with points on the real line with insertion times and
intervals with times is given as follows.

σ point x ∈ R with
point (x, t) ∈ R2 −→
insertion time t

bottomless rectangle σ interval I = [`, r]

−→
R = [`, r] × (−∞, t] with time t
It is straightforward to check that a set Y of points in the plane can be
captured by some bottomless rectangle if and only if the corresponding interval
I at time t captures the points on the real line that correspond to Y . We refer
to Figure 73(b) for an illustration.
Hence we can transfer the offline setting of points in the plane with respect
to bottomless rectangles to the online setting of points on a line with respect to

87
intervals. Now if we want to color the points in X in the plane, we can instead
online color the corresponding points that appear on the real line. This can
be seen as sweeping the point set X with a horizontal line starting at −∞ and
moving up, and coloring every point of X when it is reached by the sweepline
without considering the points above the sweepline. In particular, when we decide
which color we want to give the point p ∈ X then this depends only on the points
below p and the way we already colored these points and is independent of how
the points above p are arranged.
Hence coloring Im online can only be more difficult then coloring the point
set X with respect to m-big bottomless rectangles offline, which establishes the
claimed inequality.
We want to use the inequality in Lemma 5.2 to get an upper bound on
the k-chromatic number of any point set X in the plane with respect to m-big
bottomless rectangles. Let us first consider the case m = k, just like we did for
ranges that are decreasing curves in Theorem 5.9.
Theorem 5.11. For all k ∈ N we have

χON
k (Ik ) ≤ 2k − 1.

Proof. At the arrival of a new point p denote by (`1 , . . . , `k−1 ) and (r1 , . . . , rk−1 )
the k − 1 points to its left and to its right, respectively. Together these 2k − 2
points have at most 2k − 2 colors. Thus, there is at least one of the 2k − 1 colors
unused among these points. It is easy to see that if we color p with that color,
then all intervals capturing k points contain k different colors.
With the second part of Lemma 5.2 we can immediately draw the following
corollary.
Corollary 5.2. For every k ∈ N and every hypergraph H = (X, Fk ) with respect
to k-big bottomless rectangles we have

χk (H) ≤ 2k − 1.

Perhaps surprisingly, the easy-to-prove bound in Theorem 5.11 is best pos-

sible. Even stronger, the bound in Corollary 5.2 is best possible.
Theorem 5.12. For every k ∈ N there is a point set Xk in the plane such that
χk ((X, Fk )) = 2k − 1. In particular with Lemma 5.2 and Theorem 5.11 we have

max{χk ((X, Fk )) | X point set in the plane} = χON

k (Ik ) = 2k − 1.

Proof. We consider the point set Xk consisting of k points of the form {(i, 2i) |
0 ≤ i ≤ k − 1} and k − 1 points of the form {(2k − i, 2i − 1) | 1 ≤ i ≤ k − 1}.
See Figure 74 for an illustration.
It is easy to see that every pair of points in such a point set is in some k-big
bottomless rectangle. Thus if every k-big bottomless contains k different colors,
then no two points of Xk can be colored the same, which gives χk (Xk ) = |Xk | =
2k − 1.

88
 Figure 74: A point set Xk with χk (Xk ) = |Xk | = 2k − 1 for k = 4.

We have seen that if we want to color points in the plane with respect to
bottomless rectangles, then it can be very useful to simply sweep the points
bottom to top and color points as they appear without considering the points
above the sweepline. In particular, Theorem 5.12 states that we can find a
k-good c-coloring with respect to m-big bottomless rectangles and small c this
way, provided m = k. However, for different values of m the situation can
change drastically. For example if we want to bound

m(k) = min{m ∈ N | ∀X ⊂ R2 : χk ((X, Fm )) = k}.

For convenience let us define similarly to m(k) the following quantity.

def
mON (k) = min{m ∈ N | χON
k (Im ) = k}.

Clearly, we have by Lemma 5.2 for all natural number k that

m(k) ≤ mON (k). (13)

However, inequality (13) turns out to be a very poor estimate.

Lemma 5.3. For every m ≥ 2 we have χON
2 (Im ) ≥ 3. In particular,

mON (k) = ∞ for every k ∈ N.

Proof. We fix m ∈ N and shall show that there is no online 2-good 2-coloring
Φ of Im . That is, we shall describe an adversarial strategy to present points on
the real line so that no matter how every point is colored by Φ (either red or
blue) we can force a set of m consecutive points that are all colored the same.
Indeed, the strategy is easy: Always present the next point to the right of
all red points and to the left of all blue points. It is easily seen that as soon as
2m − 1 points are presented the m leftmost points are all red or the m rightmost
points are all blue.
We will see next that m(k) < ∞ for every k ∈ N, which makes inequality (13)
basically useless. However, we remark that for a different type of range (other
than bottomless rectangles) the analogous inequality could be very valueable.
To prove that m(k) < ∞ we consider a new variant of the online (c, k)-coloring
problem, which is actually just a slight weakening of the properties (O1)–(O4)
that have to be fulfilled by every online k-good c-coloring Φ.

5.4 Semi-Online Coloring Problems

Recall that loosely speaking every online k-good c-coloring has to satisfy the
following for every hypergraph that is presented vertex by vertex.

89
(O1) Color every vertex immediately when it appears.
(O2) Use at most c colors.

(O3) Never recolor any vertex.

(O4) Ensure that every hyperedge contains vertices of at least k different colors.

A semi-online k-good c-coloring also satisfies (O2)–(O4) but it does not

have to satisfy (O1). This means that a vertex can be left uncolored when
it appears. For completeness we then have to add the possibility of coloring
vertices that were left uncolored on their arrival.

(O5) At any time any uncolored vertex can be assigned any color.

More formally we define a partial k-good c-coloring of a hypergraph H =

(X, F) to be coloring of a subset of vertices of H with at most c colors such
that every hyperedge Y ∈ F contains vertices of at least k distinct colors. Then
the semi-online (c, k)-coloring problem is the same as the online (c, k)-coloring
problem where we simply replace every appearence of ”coloring“ by ”partial
coloring“.
Definition 5.9 (Semi-online (c, k)-coloring problem).
Let C be a class of hypergraphs. A semi-online k-good c-coloring of C is a class
Φ of exactly one partial k-good c-coloring φ for each H ∈ C and each ordering
of the vertices in H, such that the following is true.
• Whenever the vertex orderings of two hypergraph H, H 0 ∈ C coincide in
the first n positions for some n, then the corresponding partial colorings
φ and φ0 coincide on these first n vertices, too.
The semi-online k-chromatic number of C is then defined as
def
χS-ON
k (C) = min{c ∈ N | there exists a semi-online k-good c-coloring of C}.

We get the following relations between the three versions of the (c, k)-coloring
problem that we considered here: offline, online and semi-online.
Lemma 5.4. For every class C of hypergraphs and every natural number k we
have
max{χk (H) | H ∈ C} ≤ χS-ON
k (C) ≤ χON
k (C).

Proof. The first inequality holds since presenting a hypergraph H ∈ C with

one vertex at a time cannot make it easier to find a k-good c-coloring of H.
The second inequality follows as every online k-good c-coloring of C is also a
semi-online k-good c-coloring of C.

Let us come back to the class of hypergraphs induced by finite point sets in
the plane and m-big bottomless rectangles and the class Im induced by points
appearing on a line and m-big intervals at any time. Similarly to m(k) and
mON (k) we can now define
def
mS-ON (k) = min{m ∈ N | χS-ON
k (Im ) = k}

90
 and obtain as a consequence of Lemma 5.2 and Lemma 5.4 that for every
k ∈ N we have

m(k) ≤ mS-ON (k) ≤ mON (k). (14)

By Lemma 5.3 we have that mON (k) = ∞ for every k. However, in the
semi-online setting we can do much better.
Theorem 5.13. For every k ≥ 2 we have

mS-ON (k) ≤ 3k − 2.

Proof. Points appear on the real line and we need to color them with k colors
in a semi-online way so that at all times every occurrence 3k − 2 consecutive
points contain at least one point from each of the k colors.
We define a gap for color i as a maximal set of consecutive points containing
no point of color i, that is, either between two successive occurrences of color i,
or before the first occurrence (first gap), or after the last occurrence (last gap),
or all the points if no point has color i. A gap is simply a gap for color i, for
some 1 ≤ i ≤ k. Observe that k-goodness with respect to (3k − 2)-big intervals
is equivalent to the fact that at all times all gaps have size at most 3k − 3.
We propose a semi-online k-coloring that leaves the first k − 1 points uncol-
ored and from then on maintains the following invariant:

• The size of every gap is between k − 1 points (included) and 3k − 3 points

(included).

This invariant is vacuous when there are only k − 1 (uncolored) points. Now,
suppose that the invariants hold for an intermediate set of points and consider a
new point that appears on the line. Clearly, the lower bound on the size of gaps
cannot be violated in the extended set as no gaps decrease in size. However,
there may arise some gaps of size 3k − 2 violating the upper bound. If not then
the invariant holds for the extended set and the semi-online coloring does not
color any point in this step.
Suppose there are some gaps of size 3k − 2, consider one of them, say a gap
of color i, and denote the points in the gap in their natural ordering on the line
from left to right as (`1 , . . . , `k−1 , m1 , . . . , mk , r1 , . . . rk−1 ). Now, color i does
not appear among these points. The lower bound in our invariant yields that
none of the k − 1 remaining colors (those different from i) appears twice among
m1 , . . . , mk . Thus, there is some mj , which is uncolored and we color it with
color i. This splits the large gap for color i into two smaller gaps. Moreover,
since there are k − 1 `-points and k − 1 r-points these two smaller gaps have size
at least k − 1, i.e., the lower bound in the invariant is maintained for all gaps.
We refer to Figure 75 for an illustration.
The algorithm repeats that process until all gaps are of size at most 3k − 3.
Note that the treatment of one such gap requires only the validity of the lower
bound in the invariant and thus these gaps can be treated one after another.
With the first inequality in (14) we conclude the following.

91
 `1 . . . `k−1 m1 . . . mk r1 . . . rk−1

new gaps for color red

Figure 75: A gap for color red of size 3k − 2 that is split into two gaps of size
at least k − 1 each. Here k = 5.

Corollary 5.3. For every k ∈ N every finite set of points in the plane can be
colored with k colors such that every m-big bottomless rectangle contains all k
colors, provided m ≥ 3k − 2. In other words,

m(k) ≤ 3k − 2.

Perhaps surprisingly, Corollary 5.2 is the best bound on m(k) that we know
of. We do not even know whether there is a number k where m(k) and mS-ON (k)
disagree. Anyways, we can conclude that the first inequality in (14) is much
better than the second. In especially, consider semi-online colorings instead of
online colorings allowed us to prove much better results for the offline setting.
Next we will show that it is not always the case that semi-online considerations
give good results at all.
To this end, recall that in the dual (c, k)-coloring problem with respect to
bottomless rectangles we are given a finite set X ∗ of bottomless rectangles and
want to color them with at most c colors such that whenever m bottomless
rectangles are pierced by some point of the plane among these m rectangles
we see at least k different colors. Moreover, in case c = k, i.e., for k-good
k-colorings, we have defined

m∗ (k) = min{m ∈ N | max χk ((X ∗ , Fm

∗
)) = k}.
X ∗ set of bottomless rectangles

Again, we can try to prove that m(k) < ∞ by considering an appropiate on-
line or semi-online coloring problem. Just like in the primal setting we consider
a horizontal sweep line, but this time we start above all rectangles and move
the sweepline down. When we hit a bottomless rectangles this corresponds to
an interval appearing on the real line. And a set Y of bottomless rectangles is
pierced by some point in the plane if and only if there is a time and a point
on the real line that is contained in exactly the intervals corresponding to the
rectangles in Y .
∗
Hence we define Im to be the class of hypergraphs that admit the following
∗
representation. Every vertex in a hypergraph H ∈ Im corresponds to an interval
on the real line together with a number, its insertion time. And an m-set Y of
intervals form a hyperedge if and only if there is a point p ∈ R and a number
t such that Y is exactly the set of intervals that contain p and have insertion
time at most t.
If we define

92
 m∗ON (k) = min{n ∈ N | χON ∗
k (Im ) = k},

m∗S-ON (k) = min{n ∈ N | χS-ON

k
∗
(Im ) = k},

then analogously to (14) we obtain the following chain of inequalities for

every natural number k.

m∗ (k) ≤ m∗S-ON (k) ≤ m∗ON (k) (15)

It can be shown that m∗ (k) ∈ O(k 6 ) for every k ∈ N. However, both

inequalities in (15) are useless because of the next theorem.
Theorem 5.14. For every m ∈ N we have
∗
χS-ON
2 (Im ) = ∞.

In particular, m∗S-ON (2) = ∞.

Proof. For all natural numbers m and c we shall provide an adversarial strategy
to present intervals on the real line such that these intervals cannot be colored in
semi-online fashion with at most c colors so that every m-deep point is contained
in intervals of two distinct colors. Here a point of the real line is m-deep if it is
contained in exactly m so far presented intervals.
We fix c the number of colors. We shall define for every m and n an adver-
sarial strategy S(m, n) for presenting intervals such that the following is true:
∗
(i) Every semi-online 2-good c-coloring Φ of Im colors the intervals in S(m, n)
such that there are c points p1 , . . . , pc and for i = 1, . . . , c point pi is
covered by exactly ti intervals, all of which have color i, and
(ii) t1 + . . . + tc ≥ n.

Clearly, if for some semi-online c-coloring Φ there is eventually a point that is

at least m-deep and all intervals containing it have the same color, then Φ is not
2-good with respect to m-deep points. Thus if S(m, cm) exists and satisfies (i)
∗
and (ii), then there is no semi-online 2-good c-coloring of Im , which proves the
theorem.
We prove the existence of S(m, n) by double-induction on m and n. Strate-
gies S(m, 0) are vacuous as (i) and (ii) for n = 0 hold for the empty set of
intervals and any set of c distinct points p1 , . . . , pc . We define S(m, n), for
n > 0, once we have defined S(m − 1, c(m − 1)) and S(m, n − 1).
Before continuing let us present the following useful claim.
Claim. Given a set Y of intervals already presented and any I 0 ⊂ I ∈ Y with
I 0 ∩ J = ∅ for all J ∈ Y \ I. If S(m − 1, c(m − 1)) exists we can present the
intervals of S(m−1, c(m−1)) inside I 0 forcing any semi-online 2-good c-coloring
∗
of Im to color I.
Proof. We present the intervals for S(m − 1, c(m − 1)) completely inside I 0 . If
the coloring does not color I then it can be seen as a 2-good c-coloring with
respect to (m − 1)-deep points executed against S(m − 1, c(m − 1)). We already
∗
know that no such coloring exists and therefore every 2-good c-coloring of Im
has to color interval I.

93
 Now, we are ready to define S(m, n) for n > 0. First present two families
of intervals, both realizing strategy S(m, n − 1), disjointly next to each other.
By (i) there exist two sets of c points each, p1 , p2 , . . . , pc and p01 , . . . , p0c , and
non-negative integers t1 , . . . , tc , t01 , . . . , t0c such that pi is ti -covered and all its
intervals are colored with i and also p0i is t0i -covered and all its intervals are
colored with i, for every i = 1, . . . , c. Moreover, by (ii) we have t1 + . . . + tc ≥ n
and t01 + . . . + t0c ≥ n.
If there exists some i ∈ {1, . . . , c} with ti 6= t0i then the sequence of maxima
mi = max(ti , t0i ) satisfies m1 + . . . + mc ≥ n + 1. Thus, taking for each i ∈
{1, . . . , c} the point from {pi , p0i } that corresponds to the larger value of ti , t0i ,
we obtain a set of c points satisfying (i) and (ii).

S(m, n − 1) S(m, n − 1) S(m − 1, c(m − 1))

I
Figure 76: Defining strategy S(m, n) once S(m − 1, c(m − 1)) and S(m, n − 1)
are defined, in the case ti = t0i for all i ∈ {1, . . . , c}.

Hence we assume without loss of generality that ti = t0i for all i ∈ {1, . . . , c}.
Then we present one additional interval I that contains all the points p01 , . . . , p0c
but none of the points p1 , . . . , pc . Moreover, I is chosen big enough so that
there exists some I 0 ⊂ I that is disjoint from all the other intervals presented
so far. We present the intervals realizing strategy S(m − 1, c(m − 1)) inside
I 0 , forcing I to be colored, see Figure 76. Let j be the color of I. Then p0j is
now contained in exactly t0j + 1 intervals all of which are colored with j. Thus
({p1 , . . . , pc } \ pj ) ∪ p0j is a set of c points satisfying (i) and (ii), which concludes
the proof.

94
References
[ABDF+ 11] Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Tillmann Miltzow,
Rom Pinchasi, Torsten Ueckerdt, and Ran Ziv. Points with large
quadrant depth. Journal of Computational Geometry, 2(1):128–
143, 2011.
[ACC+ 11] Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori,
Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar
Smorodinsky, and Perouz Taslakian. Colorful strips. Graphs and
combinatorics, 27(3):327–339, 2011.
[ACNS82] Miklós Ajtai, Vašek Chvátal, Monroe M Newborn, and Endre
Szemerédi. Crossing-free subgraphs. North-Holland Mathematics
Studies, 60:9–12, 1982.
[Bar60] Emile Barbier. Note sur le probleme de l’aiguille et le jeu du joint
couvert. J. math. pures appl, 5(273-286):96–102, 1860.
[BDP05] Sergey Bereg, Adrian Dumitrescu, and János Pach. Sliding disks
in the plane. In Jin Akiyama, Mikio Kano, and Xuehou Tan, ed-
itors, Discrete and Computational Geometry, volume 3742 of Lec-
ture Notes in Computer Science, pages 37–47. Springer Berlin Hei-
delberg, 2005. ISBN 978-3-540-30467-8. URL [Link]
org/10.1007/11589440_4.
[BDPZ10] Itay Ben-Dan, Rom Pinchasi, and Ran Ziv. On a problem about
quadrant-depth. Computational Geometry, 43(6):587–592, 2010.
[Bla15] Wilhelm Blaschke. Konvexe Bereiche gegebener konstanter Bre-
ite und kleinsten Inhalts. Mathematische Annalen, 76(4):504–513,
1915.
[BLP07] Hervé Brönnimann, Jonathan Lenchner, and János Pach. Oppo-
site-quadrant depth in the plane. Graphs and Combinatorics, 23
(1):145–152, 2007.
[Chu36] Alonzo Church. An unsolvable problem of elementary number the-
ory. American journal of mathematics, 58(2):345–363, 1936.
[CS93] Judit Csima and ET Sawyer. There exist 6n/13 ordinary points.
Discrete & Computational Geometry, 9(1):187–202, 1993.
[CS95] J Csima and ET Sawyer. The 6n/13 theorem revisited. Graph
Theory, Cobinatorics, and Applications, 1:235–249, 1995.
[dBE51] Nicolaas Govert de Bruijn and Paul Erdős. A colour problem for
infinite graphs and a problem in the theory of relations. Nederl.
Akad. Wetensch. Proc. Ser. A, 54:371–373, 1951.
[Dir51] Gabriel A Dirac. Collinearity properties of sets of points. The
Quarterly Journal of Mathematics, 2(1):221–227, 1951.
[EG73] Paul Erdős and Richard K Guy. Crossing number problems. The
American Mathematical Monthly, 80(1):52–58, 1973.

95
[ER56] Paul Erdős and Richard Rado. A partition calculus in set the-
ory. Bulletin of the American Mathematical Society, 62(5):427–489,
1956.

[Erd46] Paul Erdős. On sets of distances of n points. The American Math-

ematical Monthly, 53(5):248–250, 1946.
[Erd78] Paul Erdős. Some applications of graph theory and combinatorial
methods to number theory and geometry. Algebraic Methods in
Graph Theory, vols. I, II, Szeged, pages 137–148, 1978.
[ES35] Paul Erdős and George Szekeres. A combinatorial problem in ge-
ometry. Compositio Mathematica, 2:463–470, 1935.
[ES60] Paul Erdős and George Szekeres. On some extremum problems in
elementary geometry. In Annales Univ. Sci. Budapest, pages 3–4,
1960.
[Fár48] István Fáry. On straight-line representation of planar graphs. Acta
Univ. Szeged. Sect. Sci. Math., 11:229–233, 1948.
[Gal44] Tibor Gallai. Solution to problem number 4065. American Math-
ematical Monthly, 51:169–171, 1944.
[Ger08] Tobias Gerken. Empty convex hexagons in planar point sets. Dis-
crete & Computational Geometry, 39(1-3):239–272, 2008.
[GK10] Larry Guth and Nets Hawk Katz. On the Erdős distinct distance
problem in the plane. ArXiv e-prints, November 2010. URL http:
//[Link]/abs/1011.4105.
[GL88] András Gyárfás and Jenö Lehel. On-line and first fit colorings of
graphs. Journal of Graph theory, 12(2):217–227, 1988.
[GRS80] Ronald L Graham, Bruce L Rothschild, and Joel H Spencer. Ram-
sey theory, volume 2. Wiley New York, 1980.
[GT13] Ben Green and Terence Tao. On sets defining few ordinary lines.
ArXiv e-prints, March 2013. URL [Link]
4714.
[HJ63] Alfred W Hales and Robert I Jewett. Regularity and positional
games. Transactions of the American Mathematical Society, 106
(2):222–229, 1963.
[Hor83] Joseph D Horton. Sets with no empty convex 7-gons. Canadian
Mathematical Bulletin, 26(4):482, 1983.

[Kaw09] Bernd Kawohl. Convex sets of constant width. page 4, 2009. URL
[Link]
[KM58] Leroy M Kelly and William OJ Moser. On the number of ordinary
lines determined by n points. Canad. J. Math, 10:210–219, 1958.

96
[KMS84] Daniel Kornhauser, Gary Miller, and Paul Spirakis. Coordinat-
ing pebble motion on graphs, the diameter of permutation groups,
and applications. In 25th Annual Symposium on Foundations of
Computer Science (FOCS), pages 241–250. IEEE, 1984.
[Kos09] Vitalii Anatol’evich Koshelev. On Erdős-Szekeres problem for
empty hexagons in the plane. Modelirovanie i Analiz Informat-
sionnykh Sistem [Modeling and Analysis of Information Systems],
16(2):22–74, 2009.

[KT04] Nets Hawk Katz and Gábor Tardos. A new entropy inequality
for the Erdős distance problem. Contemporary Mathematics, 342:
119–126, 2004.
[Leb14] Henri Lebesgue. Sur le problème des isopérimètres et sur les do-
maines de largeur constante. Bull. Soc. Math. France, CR, 42:
72–76, 1914.
[Lei84] Frank Thomson Leighton. New lower bound techniques for VLSI.
Mathematical Systems Theory, 17(1):47–70, 1984.
[MLP87] P. Mani-Levitska and János Pach. Decomposition problems for
multiple coverings with unit balls. 1987.
[Mot67] Theodore S Motzkin. Nonmixed connecting lines. Notices of the
American Mathematical Society, 14:837, 1967.
[Nic07] Carlos M Nicolás. The empty hexagon theorem. Discrete & Com-
putational Geometry, 38(2):389–397, 2007.
[Ove02] Mark Overmars. Finding sets of points without empty convex 6-
gons. Discrete & Computational Geometry, 29(1):153–158, 2002.
[Pac86] János Pach. Covering the plane with convex polygons. Discrete &
Computational Geometry, 1(1):73–81, 1986.

[PRTT06] János Pach, Rados Radoicic, Gábor Tardos, and Géza Tóth. Im-
proving the crossing lemma by finding more crossings in sparse
graphs. Discrete & Computational Geometry, 36(4):527–552, 2006.
[PT97] János Pach and Géza Tóth. Graphs drawn with few crossings per
edge. Combinatorica, 17(3):427–439, 1997.
[PT09] János Pach and Géza Tóth. Decomposition of multiple coverings
into many parts. Comput. Geom. Theory Appl., 42(2):127–133,
2009.
[PTT07] János Pach, Gábor Tardos, and Géza Tóth. Indecomposable cov-
erings. In Discrete Geometry, Combinatorics and Graph Theory,
pages 135–148. Springer, 2007.
[Rad45] Richard Rado. Note on combinatorial analysis. Proceedings of the
London Mathematical Society, 2(1):122–160, 1945.

97
[Rad46] Richard Rado. A theorem on general measure. Journal of the
London Mathematical Society, 1(4):291–300, 1946.

[Ram30] Frank Plumpton Ramsey. On a problem of formal logic. Proceedings

of the London Mathematical Society, 2(1):264–286, 1930.
[ST01] József Solymosi and Csaba D Tóth. Distinct distances in the plane.
Discrete & Computational Geometry, 25(4):629–634, 2001.
[STJ83] Endre Szemerédi and William T Trotter Jr. Extremal problems in
discrete geometry. Combinatorica, 3(3-4):381–392, 1983.
[Szé97] László A Székely. Crossing numbers and hard Erdős problems in
discrete geometry. Combinatorics, Probability, and Computing, 6:
353–358, 1997.

[Tar03] Gábor Tardos. On distinct sums and distinct distances. Advances

in Mathematics, 180(1):275–289, 2003.
[TV93] Helge Tverberg and Siniša Vrecica. On generalizations of Radon’s
theorem and the ham sandwich theorem. European Journal of
Combinatorics, 14(259-264):9, 1993.

[TV98] Géza Tóth and Pavel Valtr. Note on the Erdős-Szekeres theorem.
Discrete & Computational Geometry, 19(3):457–459, 1998.
[Tve66] Helge Tverberg. A generalization of Radon’s theorem. Journal of
the London Mathematical Society, 41(1):123–128, 1966.

[Tve81] Helge Tverberg. A generalization of Radon’s theorem II. Bull.

Austral. Math. Soc, 24(3):321–325, 1981.
[Val92] Pavel Valtr. Convex independent sets and 7-holes in restricted
planar point sets. Discrete & Computational Geometry, 7(1):135–
152, 1992.

[vdW27] Bartel Leendert van der Waerden. Beweis einer baudetschen ver-
mutung. Nieuw Arch. Wisk, 15(2):212–216, 1927.
[Viz64] Vadim G Vizing. On an estimate of the chromatic class of a p-
graph. Diskretnyĭ Analiz, 3(7):25–30, 1964.

[Wit52] Ernst Witt. Ein kombinatorischer satz der elementargeometrie.

Mathematische Nachrichten, 6(5):261–262, 1952.

98