Best Paper Award for Matfyz

The 50^th annual WG conference (50^th 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 n⁴ of them. Let's note that the upper bound was known, because we have n points, thus asymptotically n² lines determined by pairs of points; these lines divide the plane into asymptotically n⁴ 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.