Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - CombiCompGeom (Combinatorial Aspects of Computational Geometry)

Teaser

The project addresses long-standing combinatorial problems at the heart of Computational Geometry. Computational Geometry is a branch of Theoretical Computer Science dedicated to solving basic geometric problems using effective algorithms. Its practical importance lies in its...

Summary

The project addresses long-standing combinatorial problems at the heart of Computational Geometry.

Computational Geometry is a branch of Theoretical Computer Science dedicated to solving basic geometric problems using effective algorithms.
Its practical importance lies in its numerous applications to mathematical programming, computer graphics, robotic motion planning, geographic information systems, computational biology, and many other areas.
Combinatorial or Discrete Geometry is an established and fascinating branch of pure mathematics which studies the combinatorial aspects of discrete geometric structures. It bears strong relations to such well-established mathematical areas
as algebraic topology, algebraic geometry, probability theory, graph theory and extremal combinatorics.

The most fundamental questions in Computational Geometry are expressed in the terms of arrangements, Voronoi diagrams, polytopes, intersection graphs, and other abstract structures from combinatorial geometry.
Thus, design and analysis of efficient geometric algorithms is (typically) based on understanding the combinatorial complexity of these key objects studied in Discrete Geometry, and on being able to manipulate them efficiently.


The project \'Combinatorial Aspects of Computational Geometry\' explores the fruitful interplay between the two areas by addressing outstanding combinatorial questions at the heart of computational geometry.
Moreover, it demonstrates that some classical problems in combinatorial geometry can be successfully tackled using approaches that emerged within computational geometry.
Thus, project strengthens the existing bridges between the two academic communities.

Work performed

Several breakthrough results can be attributed to the project:

1. The PI has achieved the first progress in 25 years towards understanding the true asymptotic growth rates of weak epsilon-nets with respect to convex sets in the Euclidean plane.
The study of epsilon-nets is central to computational geometry, as they determine the performance of the best known algorithms for geometric hitting set/set-cover problems, and are used in most divide-and-conquer schemes.
It is a decades-old open problem to determine whether the growth rates of (optimal) weak-epsilon nets with respect to convex sets in the Euclidean space overly resemble those of strong epsilon-nets.
We achieve the first progress in 25 years by improving the 1992 planar bound of Alon, Barany, Furedi and Kleitman.

2. The PI\'s collaboration with J. Pach and G. Tardos shows that any finite set of points in the Euclidean plane determines almost linearly many pairwise crossing segments, and the result extends to all sufficiently dense geometric graphs.

Notice that the cornerstone Crossing Lemma (1982) in combinatorial geometry yields a tight relation between the number of edges in a geometric graph and the number of edge crossings in its planar embedding. The result bears enormous importance to computational geometry.
Unfortunately, the Crossing Lemma tells very little, if at all, of the underlying intersection structure (i.e., intersection graph) of the edges, and very little progress has been achieved in the passed decades.

Our lower bound on pairwise crossing edges is almost tight, and improves a much weaker 1990 lower bound of Aronov, Erdos, Goddard, Klugerman, Kleitman, Pach and Schulman.

3. Another collaboration of the PI with J. Pach and G. Tardos establishes an analogue of the Crossing Lemma for contact graphs of Jordan curves in the plane. That is, we establish a non-trivial relation between the number of touchings (i.e., points of tangency which occur if the two involved curves intersect only once) and the overall number of their intersection points in a family of Jordan curves. In particular, we establish the 1995 Richter-Thomassen Conjecture for families of closed Jordan curves.

Final results

In the following years we expect to capitalize on the above breakthroughs, the most significant of which concerns the asymptotic growth rates of optimal weak epsilon nets with respect to convex sets.
The result rests on the surprising connection between epsilon-nets with respect to convex sets and the incidence geometry of points and lines.

We also hope that the recent lower bound on the number of pairwise crossing edges will extend to more general geometric graphs, which will eventually lead to comparable gains in the related numerous open problems in combinatorial and computational geometry.

We plan to explore the discover and exploit further relations between the various powerful paradigms which emerged in various sub-communities with discrete and computational geometry (e.g., applications of the hypergraph container method to epsilon nets and transversal numbers, algebraic methods, geometric Ramsey-type results etc).