The objective of this project is to explore several problems and directions in Combinatorial Geometry and Ramsey Theory and their interconnections. One research direction is centered around the problem of geometric incidences between points and curves and their connections with problems involving distances, areas, and other measures. The project also deals with geometric questions in Ramsey theory, applications of Van der Waerden's theorem on arithmetic progressions and new results of this type, and others that fit in the broader category of monotone paths in line arrangements. Of particular interest are techniques that permit reformulations of geometric problems in a purely combinatorial setting, such as the technique of allowable sequences introduced by Goodman and Pollack. The last category comprises problems of estimating the size of sets that appear in the theory of set addition and multiplication. Ramsey type problems and Erdos-type extremal discrete geometry problems have attracted continued attention in the combinatorics and computational geometry communities, due to their relevance for computational problems (in range counting, pattern matching, motion planning, and others) and the rich techniques developed for improving extremal bounds (such as the epsilon-net theory, the Crossing Lemma, quasi-planar graphs, etc.), which proved to be instrumental in many areas of computational geometry.
A key objective of this project is to explore and identify new techniques for dealing with incidence and distance problems, and other problems in Ramsey theory and number theory that seem to require attacks from several directions. An important feature of the proposed research is advancing the integration of techniques from different areas---geometric graph theory, number theory, topology, linear programming, computer experiments, theory of algorithms---in finding solutions for problems in combinatorial geometry and Ramsey theory. Progress on some of the combinatorial questions presented here are likely to have applications in the design and analysis of geometric algorithms, approximation algorithms, etc, and consequently have impact in the real word over time.
The Project was set to explore several problems and directions in Combinatorial Geometry and Ramsey Theory and their interconnections. More than 20 conference publications and more than 20 journal publications have resulted, that acknowledge support from this grant. Results have been presented at prestigious international venues, such as the Annual Sympos. on Comput. Geometry (SOCG), and the Annual ACM-SIAM Sympos. on Discrete Algor. (SODA), and further appeared in peer reviewed journals, such as Discrete & Computational Geometry, Combinatorics, Probability & Computing, Combinatorica. We highlight some of the results: A sharp estimate is obtained on the expected number of maximal empty axis-parallel boxes amidst $n$ random points in the unit hypercube in $d$-space. This estimate is relevant for analyzing the performance of exact algorithms for computing the largest empty axis-parallel box amidst $n$ given points in an axis-parallel box, especially the algorithms that proceed by examining all maximal empty boxes. Finding large empty gaps is often investigated in data mining. This estimate is related to the expected number of maximal (or minimal) points amidst random points, and has application to algorithms for colored orthogonal range counting. Let $S$ be a set of $n$ points in the unit square $[0,1]^2$, one of which is the origin. We construct $n$ pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in the set, and the rectangles jointly cover at least a positive constant area (about $0.09$). This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2. New lower and upper bounds are obtained for the maximum multiplicity of some weighted and, respectively, non-weighted common geometric graphs drawn on $n$ points in the plane with no three points collinear: perfect matchings, spanning trees, spanning cycles (tours), and triangulations.
