Les treillis de disques et leur implémentation

Jean Serra (A2SI, ESIEE)

Résumé:

Trouver le plus petit disque contenant une famille donnée de disques suppose qu'un tel élément minimal existe, et qu'il est unique. Nous démontrons que les disques compacts du plan euclidien forment un treillis complet pour l'ordre de l'inclusion. Les expressions explicites du supremum et de l'infimum sont données. Elles dépendent de manière simple de l'érodé ultime d'un ensemble construit à partir de dilatations des disques. La démarche s'étend à toute famille de compacts convexes homothétiques du plan, et plus généralement de Rn , à la condition que ces convexes admettent des courbures non nulles en tout point de leur frontière. Cette contrainte pose un problème de digitalisation, où il faut en général faire un choix entre plusieurs solutions, heureusement très proches.