Ces journées ont pour but de réunir les communautés de géométrie : géométrie discrète, géométrie algorithmique, modélisation géométrique, au sein du GdR Informatique Mathématique (IM) et du GdR Informatique Géométrique et Graphique, Réalité Virtuelle et Visualisation (IG-RV).

Cette édition des Journées Informatique et Géométrie est adossée aux journées du Groupe de Travail Modélisation Géométrique (GTMG). En particulier, une partie de son programme est  commun avec celuis des journées GTMG.

Yan Gerard (Université Clermont Auvergne, LIMOS)

Titre : Les heuristiques géométriques des Shadoks

(Les Shadoks : Loïc Crombez, Guilherme Da Fonseca, Aldo Gonzales-Lorenzo et Yan Gerard, plus Pascal Lafourcade et Luc Libralesso en 2021)

Résumé : Avec les Shadoks, nous avons participé aux 4 challenges internationaux d'optimisation géométrique CG:SHOP (Computational Geometry: Solving Hard Problems) qui se sont déroulés dans le cadre des dernières éditions de SoCG de 2019 à 2022. Le thème de cet exposé est de présenter les heuristiques que nous avons développées pour ces problèmes NP-durs, heuristiques que l'on pourrait sous-titrer "comment des idées simples peuvent fournir des algorithmes efficaces". 2019 - le problème du premier challenge est une variante de TSP (input: un ensemble de points du plan noté S/output: un polygone P simple de sommets S) où l'objectif est de maximiser/minimiser l'aire intérieure de P au lieu de son périmètre. Notre solution réduite à 500 lignes de code en Python (https://github.com/gfonsecabr/poLYG) combinant un algorithme gourmand avec une recherche locale nous a amené à la seconde place du challenge. 2020 - Quatrième place, la médaille en chocolat. Nous passerons vite... 2021 - Le problème relève d'une problématique appelée Multi-Agent Path Finding. Un ensemble de robots mobiles (des carrés unité) et un certain nombre d'obstacles fixes est positionné sur une grille carrée (2D). Chaque robot est donné avec une position initiale et une position d'arrivée. Le problème consiste à déplacer la flotte de robots, de case en case en évitant les collisions. Deux objectifs peuvent être considérés: minimiser la distance totale parcourue par l'ensemble des robots ou minimiser la durée entre le premier déplacement et le dernier (les robots se déplacent simultanément). Nous avons travaillé sur la minimisation de la durée en utilisant différentes stratégies pour calculer une solution initiale et une optimisation "par conflits" pour l'améliorer. Nous sommes arrivés à la première place (Code sur GitHub: https://github.com/gfonsecabr/shadoks-robots). 2022 - Le challenge (coloration du graphe d'intersection d'un ensemble de segments) se termine dans quelques jours. En fonction des résultats, je présenterai (ou pas) les stratégies utilisées...

Florent Lafarge (Inria Sophia Antipolis Méditerranée, Equipe-projet Titane)

Titre : A la recherche de schémas de partitionnement spatial efficaces pour des problèmes de vision

Résumé : Les structures de données de partitionnement spatial jouent un rôle central dans de nombreux problèmes de vision tels que la reconstruction de surface, la polygonalisation d'objets et l'extraction de réseaux linéiques : elles sont l'interface entre des données souvent non organisées et les algorithmes standardisés. Pour être efficaces, ces structures de données doivent être i) rapides à construire, ii) compactes, iii) indépendantes de la résolution des données et iv) faciles à modifier. Malheureusement, ces exigences sont rarement satisfaites par celles couramment utilisées en vision, principalement les grilles de voxels, les octrees et les triangulations qui ne permettent pas de passer à l'échelle en présence de données massives. Dans cet exposé, je présenterai d'abord un ensemble de problèmes de vision pour lesquels les schémas de partitionnement d'espace traditionnels ne permettent pas d'atteindre une grande précision et de passer à l'échelle. Je présenterai et discuterai ensuite deux structures de données alternatives conçues pour fonctionner efficacement sur ces problèmes : des partitions polyédriques 3D construites par simulations cinétiques et des triangulations de Delaunay dynamiques échantillonnées par des processus ponctuels spatiaux.

La conférence est organisée en présentiel.

Lieu : UFR Sciences et techniques, Bâtiment Mirande, 24 avenue Alain Savary, Dijon (lien google map ici).

Date : mardi 15 et mercredi 16 mars 2022. (La matinée du mercredi est commune aux JIG et aux journées GTMG : https://gtmg2022.sciencesconf.org)

Inscription : gratuite mais obligatoire. (Une aide est susceptible d'être apportée par le GdR IG-RV en cas de difficulté à financer votre mission. Le cas échéant, merci de prendre contact à l'adresse jig2022@sciencesconf.org.)

Organisateurs :

• Romain Raffin (Université Bourgogne Franche-Comté, LIB)
• Isabelle Sivignon (CNRS, Gipsa-lab)
• Géraldine Morin (Université de Toulouse, IRIT)
• Nicolas Passat (Université de Reims Champagne-Ardenne, CReSTIC)

Contact : jig2022@sciencesconf.org

Cette conférence est organisée avec le soutien logistique de l'Université de Bourgogne et avec le soutien financier des GdR IM et IG-RV du CNRS.

Cette conférence a reçu le soutien financier des sociétés DigitalSurf et SopraSteria.