Researchers have proved an old conjecture in combinatorial geometry

Israeli and European researchers succeeded in proving an old conjecture in combinatorial geometry

The researcher Dr. Natan Rubin from the Department of Computer Science at Ben-Gurion University in the Negev proved in cooperation with Prof. Yanosh Pach, from the Federal Technological Center of Switzerland andProf. Gabor Tardosh From the Alfred Reny Center for Mathematics in Budapest, an old conjecture from 1996 in combinatorial geometry.

Background for the research: The packing theorem of circles Koebe's famous 1936 provides a thorough correspondence between planar maps and packings of disks in the plane, that is, arrangements of coins without overlapping on a flat table (see image).

On the other hand, theoreticallyFor the cuts” from 1982 links the density of the network to the number of overlaps in its planar drawing, meaning “the denser a road network, the greater the number of interchanges required”.

The above results are central to combinatorial geometry and have found extensive uses in computational geometry. It is a field close to computer science that deals with solving problems of a geometric nature, which arise in a variety of fields such as robotic movement planning, map drawing, computational biology, and the like.

In the present study, the researchers proved the 1996 Richter-Thomsen conjecture by making an ambitious generalization of it. The researchers showed the parallel phenomenon to the cut-off pattern for "grids" of plane curves, which describe intersections between simple curves in a plane. This result narrows the gap between two mathematical worlds (simple curves and planar maps), and it is expected to have extensive uses in computational geometry, among others in the field of map drawing. Mathematically, this is a surprising diagnosis because until today most of the quantitative results in the field have only concerned low degree algebraic curves, such as straight lines and circles. In contrast, general simple curves have always posed an extraordinary challenge to quantitative analysis due to their uncontrollable behavior (any two curves can meet an arbitrary number of times).