Best Paper Award for Matfyz

June 28, 2024

Associate Professor Jan Kynčl and doctoral student Jan Soukup from the DiGeo discrete geometry group at the Department of Applied Mathematics of Matfyz CUNI, received an award at the international conference WG 2024 in Slovenia. They won the main prize, the Best Paper Award, for solving a problem in the field of discrete geometry.

The 50th annual WG conference (50th International Workshop on Graph-Theoretic Concepts in Computer Science), which presents the latest findings in graph theory and its applications in computer science, was held in June in the Slovenian village Gozd Martuljek. At this gathering of mathematicians, Jan Soukup, a doctoral student from Matfyz, introduced the findings from his paper Many Views of Planar Point Sets, which he worked on with his advisor, Associate Professor Jan Kynčl.

In the paper the authors investigated an open problem in the field of discrete geometry, which they successfully solved. „It's a rather intuitive question: we have a plane with n distinct points, such that no three of them are collinear. When we are at any point in the plane, we see these points in some cyclic order around us (let's call this a view). The question we solved is how many such different views always exist, regardless of how the points are arranged,“ explained Jan Soukup. „We showed that there are always asymptotically n4 of them. Let's note that the upper bound was known, because we have n points, thus asymptotically n2 lines determined by pairs of points; these lines divide the plane into asymptotically n4 parts, and within each part, the view of our set of points is always the same.“

The question itself has been known for a long time. „Determining the known upper bound is, for example, an exercise in Professor Jiří Matoušek's book Lectures on Discrete Geometry, and we have been assigning it for many years as an exercise in discrete mathematics courses at our faculty. The question of determining the lower bound has appeared in several research papers, where the motivation comes from algorithmic questions, as counting views is a necessary step in various geometric algorithms,“ outlines Jan Soukup.

„It is my first award in the field of research, so I highly value it, and I am glad that the broader community has appreciated what we are doing at Matfyz,“ adds Jan Soukup.

Charles University, Faculty of Mathematics and Physics
Ke Karlovu 3, 121 16 Praha 2, Czech Republic
VAT ID: CZ00216208