Cyril Nicaud (LIAFA, Jussieu)

En géometrie discrete 2D, un certain nombre de problèmes sont très utilisés, tels que savoir si un objet est connexe, étiqueter les composantes connexes d’un objet, mais aussi d’autres problèmes tels que determiner si deux objets donnés “ont la même topologie”.

Après avoir defini précisement un certain nombre de ces problèmes, nous exposerons un algorithme LogSpace pour déterminer si deux pixels d’un objet sont connectés ou non dans cet objet. (LogSpace signifie que l’algorithme ne peut stocker qu’un nombre borné de coordonnées de pixels, independant de la taille de l’image, les entrées étant en “read Only”). Un corollaire est que presque tous les problèmes considérés, et notament l’étiquetage des composantes connexes, sont dans LogSpace.

Ensuite, on s’attache à donner des bornes inferieures pour la complexité de ces problèmes. On montre que le problème de savoir si deux pixels dans un objet sont connectés est NC^1-difficile. Enfin, on montre qu’aucun des problèmes considérés ne peut être résolu en temps constant sur une machine parallèle avec un nombre polynomial de processeurs (plus précisement, on montre qu’aucun de ces problèmes n’est dans AC^0).