30/10/2025
Lubomír Štěpánek z Katedry statistiky a pravděpodobnosti a Katedry matematiky FIS VŠE získal na mezinárodní konferenci IEEE FedCSIS 2025 (Federated Computer Science & Intelligence Systems, CORE B v computer science, https://2025.fedcsis.org/) v polském Krakově, konkrétně v kategorii Computational Optimization, poměrně významné mezinárodní ocenění Best Paper Award za svůj aktuální článek "Improved upper bounds on the shortest watchman route in simple polygons: Dependence on reflex vertices and triangulation strategies". Ve článku se věnuje zpřesnění (tj. zmenšení) horních mezí délek nejkratší tzv. watchman route ("hlídací" cesty), tedy nějaké (obvykle lomené) čáry uvnitř nebo na hranici polygonu takové, že každý bod polygonu je "vidět" alespoň z jednoho bodu této čáry. Ve článku formálně dokazuje zpřísněné horní meze při minimální znalosti geometrie polygonu. Ač jsou důkazy v článku obvykle nekonstruktivní, lze podle jejich logiky takovou watchman route i konstruktivně sestavit, a to pomocí nově navržené triangularizace. Byť jde o zcela teoretický formální článek, aplikace jsou poměrně široké -- např. víme-li, že nejkratší "hlídací" cesta v málo známém terénu nebude delší než nějaká konstanta daná zlomkem obvodu polygonu, byť jen iniciálně nepřesně odhadnutého, pak díky výsledkům víme, že dronu, který se má po hlídací cestě pohybovat, bude stačit mít baterii nabitou třeba jen na určitou mez, a přesto bude možné celý terén tvaru polygonu prozkoumat, resp. zmapovat. Jinými aplikacemi jsou ideální, tedy co nejkratší hlídací cesty dronů nebo hlídačů např. ve výrobních halách nebo parkovištích apod. -- opět, víme-li dle plánu objektu pouze délku jeho obvodu, můžeme i bez konstrukce cesty dopředu říci, že nebude delší než nějaká konstanta odvozená z obvodu, a tedy bude pro hlídání objektu stačit pořídit malý (levný) dron s jen malou baterií. Téma lze dále rozvíjet, dr. Štěpánek říká, že by mohlo vydat ještě na několik diplomových a dizertačních prací. Nabízí se např. probabilizace problému, převod problému na celočíselnou mřížku, aplikace na nesimplexní, ortogonální nebo 3D polygony, voronoizace a další geometricko-kombinatorické triky, na kterých již pracuje, plus aplikace výsledků do praxe, např. v optimalizaci surveillance a patrolingu pomocí dronů, což je teď celosvětově velké téma, anebo preselekce lepších trénovacích dat (filtrujících pryč neoptimálně dlouhé cesty) pro trénovaní machine-learning algoritmů, které hlídací cesty konstruktivně sestavují.
