At the 36th International Workshop on Combinatorial Algorithms (IWOCA 2025), held on July 21–24, 2025, in Bozeman, USA, a team of researchers, together with Dr. Maria Saumell from FIT CTU, received the Best Paper Award for their article Guarding a 1.5D terrain with Imprecise Viewpoints.
The article was the result of collaboration among experts from several universities. The co-authors are Assoc. Prof. Pavel Valtr, Dr. (Charles University, Faculty of Mathematics and Physics), MSc. Maria Saumell, Ph.D. (Faculty of Information Technology, CTU), Msc. Vahideh Keikha, Ph.D. (Czech Academy of Sciences), and dr. Maarten Löffler (Utrecht University).
The awarded paper addresses a problem in the field of computational geometry, specifically visibility in terrains. The authors study a task in which an n-vertex “1.5D” terrain and a set of its edges are given. A guard must be placed on each edge so that the maximum portion of the terrain is covered. The team presented a simple approximation algorithm for the general version of the problem and polynomial-time algorithms for the cases with one and two guards. They also showed that the problem of finding a point from which the maximum portion of the terrain is visible can be solved in O(n³) time.
“This award is a great recognition of our joint research and an encouragement for further work in this field,” says Dr. Maria Saumell from FIT CTU.
The IWOCA workshop is a long-standing event that has brought together experts in discrete mathematics and computer science for nearly forty years. First held in Australia, it has gradually become an important international platform for sharing research results in combinatorial algorithms.
