Grant-funded Project Nr. 159/1999/B-MAT/MFF
Final Report

Project title:Discrete and Computational Geometry
Research leader:Doc.RNDr. Jan Kratochvíl, CSc.
Co-researcher: Doc.RNDr. Jiří Matoušek, DrSc.; Mgr. Pavel Valtr, Dr. Ph.D.; Mgr. Jakub Šimek, ; Mgr. Helena Nyklová
Period of project:1999-2001
Overall grant:225 000 CZK

Project Results

The researchers in this grant project and their collaborators have achieved a number of significant theoretical results in the field of combinatorial and computational geometry, which have resulted in 29 publications (published or accepted) acknowleding a partial support of the grant. The concrete results are specified in more detail in the annual reports. A summary of the most significant results follows.
- Doctoral and Masters students supervised by the grant's holders co-authored three papers accepted to international conferences "Graph Drawing": on visibility representations of complete graphs, on embeddings of trees in the plane with a minimum distortion of vertex distances, and on intersection graphs of segments with fixed directions.
- P. Valtr investigated, in several papers, generalizations of Davenmport-Schinzel sequences (for example, Davenport-Schinzel trees) and their geometric applications.
- P. Valtr with co-authors obtained quantitative bounds for the Erd"os-Szekeres theorem in higher dimensions, as well as several other results related to this theorem, such as a new nontrivial condition for the existance of en empty convex k-gon in a given sufficiently large point set in the plane.
- J.Kratochvíl with co-authors have solved several algorithmic problems concerning intersection graphs (and published a survey in this area) and concerning the colorability of clique hypergraphs.
- J. Matoušek has found a combinatorial proof of Lovász' theorem on the chromatic number of Kneser graphs, originally established by a topological method, as well as a simplified proof of a theorem on Kneser hypergraphs..
- I. Bárány and J. Matoušek have proved a fractional Helly theorem for convex lattice sets.
- They have also studied the problem of partitioning measures in the plane by k-fans. Among others, they showed that every two probability measures in the plane can simultaneously be equipartitioned by a 4-fan.