Na letošním 36. ročníku International Workshop on Combinatorial Algorithms (IWOCA 2025), který se konal ve dnech 21.–24. července 2025 v Bozemanu (USA), získal tým vědců, společně s vědkyní z FIT ČVUT dr. Marií Saumell, ocenění Best Paper Award za článek s názvem Guarding a 1.5D terrain with Imprecise Viewpoints.
Na článku spolupracovali odborníci z několika univerzit. doc. RNDr. Pavel Valtr, Dr. (MFF UK), MSc. Maria Saumell, Ph.D. z Katedry teoretické informatiky FIT ČVUT, Mcs. Vahideh Keikha, Ph.D. z Akademie věd ČR a Maarten Löffler, Ph.D. z univerzity v Utrechtu.
Oceněná práce se zabývá problémem z oblasti výpočetní geometrie, konkrétně otázkami viditelnosti v tzv. terénech. Autoři zkoumají úlohu, v níž je dáno n-vrcholové „1.5D“ prostředí a množina jeho hran. Na každou hranu je třeba umístit jednoho „hlídače“ tak, aby byl pokryt co největší úsek terénu. Tým představil jednoduchý aproximační algoritmus pro obecnou variantu problému a polynomiální algoritmy pro případy s jedním a dvěma hlídači. Dále dokázali, že problém nalezení bodu, z něhož je vidět maximální část terénu, lze vyřešit v čase O(n³).
„Toto ocenění je velkým uznáním naší společné práce a zároveň motivací do dalšího výzkumu,” říká dr. Maria Saumell z FIT ČVUT.
Workshop IWOCA patří k již tradičním akcím, kde se již téměř čtyřicet let setkávají odborníci na diskrétní matematiku a informatiku. Poprvé se konal v Austrálii a postupně se stal významnou mezinárodní platformou pro sdílení výsledků v oblasti kombinatorických algoritmů.
