Date : 10 février 2022 -- Type : distinction Challenge Computational Geometry : 2 équipes Limos sur le podium

Chaque année depuis 2019, le challenge CG:SHOP (Computational Geometry: Solving hard PrOblems) de résolution de problèmes difficiles est organisé en marge de la conférence de géométrie algorithmique SoCG. Le but est de résoudre un grand nombre d'instances (plus de 200) d'un problème géométrique NP-dur.

Pour cette édition 2022 (ici: https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2022/#problem-description ), 40 équipes se sont inscrites. Le LIMOS présentait deux équipes.
Le problème proposé traitait de la coloration de graphes d'intersections de segments (de 3000 à 70000 segments c'est-à-dire des graphes avec autant de sommets et plusieurs millions d'arêtes pour les plus petit graphes). C'est un problème géométrique NP-dur (comme chaque année).

Légende: l'instance du challenge vispecn2518 (2518 segments) colorée avec 57 couleurs. C'est une solution optimale car le graphe d'intersection des segments a une clique de 57 segments. Pour visualiser de façon interactive les segments de chaque couleur, vous pouvez ouvrir le lien ... dans un navigateur et cliquer sur le bandeau de couleurs pour voir les segments colorés.

L'équipe, Les shadoks composée de Guilherme Da Fonseca (LIS), Aldo Gonzalez-Lorenzo (LIS), Loïc Crombez (LIMOS) et Yan Gerard (LIMOS), participait pour la quatrième fois. Elle a remporté la première place avec un score optimal de 225 sur 225 (meilleure solution trouvée sur chacune des 225 instances proposées). Félicitations à Loïc pour son importante contribution. L'équipe remercie en particulier tout les responsables des serveurs de calcul du LIMOS dont les ressources ont été précieuses.

La seconde équipe composée de Florian Fontan, Pascal Lafourcade (LIMOS), Luc Libralesso (ancien post-doc LIMOS) et Benjamin Momège (post-doc Inria Lille) arrive en 3e position avec un score de 211/225 (calculé à partir des meilleures solutions de tout le monde). Bravo!

Pour se faire une idée d'une solution optimale, cliquez sur le lien ci-dessous. La solution s'ouvre dans un navigateur et on peut cliquer sur le bandeau de couleurs pour voir les segments colorés avec chaque couleur.

https://perso.limos.fr/~basdorea/vispecn2518-57colors-daft.sol.svg

https://drive.uca.fr/f/8daf52c50e364c538d8d/

https://drive.uca.fr/f/8daf52c50e364c538d8d/