To: seminaire@pauillac.inria.fr From: Bruno.Barras@inria.fr Subject: SEM - INRIA : LogiCal - 26/06/01 - Paris - FR Vous pouvez maintenant vous abonner à nos annonces de séminaires http://pauillac.inria.fr/seminaires/subscribe.html S E M I N A I R E . ___ / _ _ / _ / / / \ / \ / / __| / |___ |_/ |_/ / |__ |_/ |_ ___ . / / ___ __ /_ _ / _/ /| /| _ __ __ _ _ / / / /_ / __| / / |/ | / \ /_ / / \ | / __| |___ / / __/ |_ |_/ |_ / | |_/__/ |_ |_/ |/ |_/ I N R I A - Rocquencourt Salle de conference du Bat 11 Mardi 26 juin, 14h00 --------------------------------------------------- Yves Bertot (Travaux effectué avec David Pichardie, ENS Cachan) --------------------------------------------------- ================================================ Formalisation d'algorithmes d'enveloppe convexes ================================================ Nous avons formalisé deux algorithmes de calcul d'enveloppe convexe en dimension 2. Pour ces deux formalisations, nous avons d'abord étudié les propriétés générales des enveloppes convexes, en commençant par les 5 propriétés de base de la fonction d'orientation, qui est utilisée pour décrire si les points d'un triangle sont énumérés dans le sens trigonométrique ou dans le sens des aiguilles d'une montre. Cette approche permet de faire une étude assez complète en mettant entièrement de coté les aspects numériques du calcul. Cette approche permet de décrire des algorithmes qui fonctionnent très bien lorsque la donnée est en position générale, c'est-à-dire que trois points distincts ne sont jamais alignés. Pour un algorithme qui fonctionne dans tous les cas, il est nécessaire de considérer aussi les positions dégénérées. Pour cette étude nous avons explorés deux directions. La première consiste à inclure dans l'algorithme des test d'appartenance à des segments et à compléter les propriétés fondamentales proposées par Knuth pour incorporer les relations entre triangles et segments. La seconde direction repose sur une notion élégante de perturbation qui permet d'associer une orientation au triplets de points même lorsque ceux-ci sont alignés, tout en conservant les propriétés de cohérences décrites par Knuth.