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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

• People
  • Personnel
  • Guests
  • Alumni
• Reports
  • Current Report
  • Report for 2023
  • Report for 2022
  • Previous Reports
• Research
  • Grants
  • Dissertations
  • Master/Bachelor Theses
  • Current Publications
  • Previous Publications
• Mittagsseminar
• Courses
• Thesis Topics
• Events
  • Workshops
    • Current
    • Previous
  • Social
    • SOLA
    • GREBGE
• 

Ramsey-Remainder for Convex Sets and the Erdös-Szekeres Theorem

Gyula Karolyi, Eötvös University, Budapest

A set of points in the d-dimensional Euclidean space $\hbox{\sf I\kern-.12em E}^d$ 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 $n>d\ge 2$, f(n,d)denote the smallest integer such that any set of at least f(n,d) points, in general position in $\hbox{\sf I\kern-.12em E}^d$, 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 $f(n,d)\le f(n,i)$, for any $2\le i<d$. We slightly improve upon this bound proving that if $n>d\ge 3$, then $f(n,d)\le f(n-1,d-1)+1$. This, in turn, yields the estimate

$$f(n,d)\le {{2n-2d-1}\choose {n-d}}+d\ .$$

As for lower bounds, we prove the following result.

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

$$f(n,d)= \Omega(c^{\root d-1 \of n})\ .$$

If we are given f(k,d) points, in general position in $\hbox{\sf I\kern-.12em E}^d$, 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 $d\ge 3$ and n is large enough, then any set of knpoints, in general position in $\hbox{\sf I\kern-.12em E}^d$, 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 4n points, in general position in the plane. There is a positive integer n₀ such that if $n\ge n_0$, then the following two statements are equivalent.

(i) P can be partitioned into n convex quadrilaterals, that is, there exist pairwise disjoint convex sets $C_1,\ldots,C_n$, each of size 4, such that $P=\cup_{i=1}^nC_i$.

(ii) There is no partition $P=A\cup^*B$ such that |A| is odd and $\vert A\cap C\vert$ is even for every convex quadrilateral $C\subset P$.

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

Corollary. There is an $O(n^2\log n)$ time algorithm which decides if a given set of 4n> 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 $n\ge 3$ 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

Imprint Disclaimer Copyright