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

Prof. Emo Welzl and Prof. Bernd Gärtner

**
Gyula Karolyi, Eötvös University, Budapest**

A set of points in the *d*-dimensional Euclidean space
is said to be
in general position if the affine hull of any *d*+1of the points is the whole space. It is called *convex* if it
is the vertex set of a convex polytope. Let, for , *f*(*n*,*d*)denote the smallest integer such that any set of at least *f*(*n*,*d*) points,
in general position in
, contains a convex set of size *n*.
The existence of *f*(*n*,*d*) and respective lower and upper bounds
were established by Erdos and Szekeres. It is not difficult to see,
that
, for any . We slightly improve upon this
bound proving that if , then
. This,
in turn, yields the estimate

As for lower bounds, we prove the following result.

Theorem.
*For every ** there exists a constant **c*=*c*(*d*)>1* such that,
if **n*>*d**, then
*

If we are given *f*(*k*,*d*) points, in general position in
, we can
separate a convex set of size *k*.
Repeating this process, eventually we obtain a
partition into convex *k*-sets, and a remaining set of size <*f*(*k*,*d*).
However, one can do it better. In fact, it is not too difficult to prove
that if and *n* is large enough, then any set of *kn*points, in general position in
, can be partitioned into *n* convex
subsets of size *k*. This is not true, however, in the planar case,
even if *k*=4. The study of this case was suggested by Joe Mitchell, who
conjectured that the corresponding decision problem was NP-complete. The
existence of a desired partition is easily shown if the convex hull of the
given points has at least 5 vertices. In general, we have the following
result.

Theorem.
*Let **P** be any set of *4*n** points, in general position in the plane.
There is a positive integer **n*_{0}* such that if **, then the
following two statements are equivalent.
*

*(i) **P** can be partitioned into **n** convex quadrilaterals, that is,
there exist pairwise disjoint convex sets *
*, each
of size 4, such that *
*.
*

*(ii) There is no partition *
* such that *|*A*|* is odd
and ** is even for every convex quadrilateral *
*.
*

The restriction on *n* is necessary. In fact, the theorem is not valid with
. On the other hand, our proof can be turned into an effective
algorithm, thus disproving Mitcell's conjecture.

Corollary.
*There is an *
* time algorithm which decides if a given set
of *4*n*> 200* points, in general position in the plane, can be
partitioned into convex quadrilaterals. Moreover, if the output is `YES',
the algorithm also returns such a decomposition.*

We also give a complete geometric description of those sets of points that violate condition (ii) in the second theorem. This may be of independent interest, since these kinds of sets often arise in connection with certain extremum problems in discrete geometry and graph theory.

Finally, if time permits, we give an account on a recent progress concerning the existence of large empty convex subsets, a joint work with János Pach and Géza Tóth. It is well known, that there are arbitrarily large planar sets without empty convex heptagons. One of our results is that if the point set is `sparse' then it contains a large empty polygon.

Definition. A set of points, in general position in the plane, is said
to be *sparse* if any triangle determined by them contains at most one
of the points in its interior.

Theorem. *For every integer ** there exists a positive integer
**e*(*n*)* such that every sparse set of at least **e*(*n*)* points in the plane
contains the vertex set of a convex **n**-gon whose interior is empty, that is,
does not contain any of the given points.*

Back