Point sets with small integer coordinates and no large convex polygons

Abstract: In 1935, ErdH{o}s and Szekeres proved that every set of

n

points in general position in the plane contains the vertices of a convex polygon of

f r a c 12 l o g_{2} (n)

vertices. In 1961, they constructed, for every positive integer

t

, a set of

n := 2^{t - 2}

points in general position in the plane, such that every convex polygon with vertices in this set has at most

l o g_{2} (n) + 1

vertices. In this paper we show how to realize their construction in an integer grid of size

O (n^{2} l o g_{2} (n)^{3})

.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Point sets with small integer coordinates and no large convex polygons