GENEPI Equipe associée Géométrica - New York University - Polytechnic University Brooklyn (proposition initiale) (bilan 2004 et demande de renouvellement 2005) (bilan 2005 et demande de renouvellement 2006) (bilan 2006 et demande de renouvellement 2007 (3ieme annee)) (bilan 2007 et demande de renouvellement 2008)

Evénements

• GENEPI se termine fin 2008 !
• Juillet-Aout 2008 : Séjour de 2 etudiants de NYU à Sophia Antipolis.

  Jihun Yu et Ben Galehouse.

• 13-20 juin 2008 : Sejour de Monique Teillaud a NYU.
  Presentation des travaux en cours a l'INRIA sur les triangulations periodiques.
  Travail sur des representations approchees de courbes.

• Septembre 2007 : Séjour d'une semaine de Chee Yap à Sophia Antipolis lors du Workshop on Robust Shape Operations WRSO.

• Juillet 2007 : Presentation a Paris dans le cadre du programme REUSSI.

  Jihun Yu et Dave Millman ont presente leurs travaux. Jihun en a profite pour etendre son sejour afin de collaborer avec Guillaume Melquiond.

• Juin 2007 : Visite d'une semaine de Guillaume Melquiond à Sophia Antipolis.

  Collaboration sur le travail de Jihun Yu.

• Juin-Juillet 2007 : Séjour de 2 etudiants de NYU à Sophia Antipolis.

  Dave Millman (8 semaines) : travail sur l'implementation de la triangulation de Delaunay 3D en parallele dans CGAL, en utilisant OpenMP, en collaboration avec Sylvain Pion.

  Jihun Yu (8 semaines) : travail sur l'implementation de la proposition de standardisation de l'arithmetique d'intervalles en C++, en se basant sur Boost.Interval et CRLIBM. En collaboration avec Sylvain Pion.

• Octobre 2006 : Séjour de Sylvain Pion a New York.

  Travail sur l'article sur la re-architecture de la bibliotheque CORE, avec Chee Yap et Jihun Yu.

• Juin-Aout 2006 : Séjour de 3 etudiants de NYU à Sophia Antipolis.

  Dave Millman (7 semaines) : travail sur les predicats du diagramme d'Apollonius, en collaboration avec Christophe Delage (etudiant en these dans Geometrica).

  Jihun Yu (8 semaines) : travail sur la bibliotheque CORE, en collaboration avec Sylvain Pion.

  Chris Wu (6 semaines) : travail sur les maillages, en collaboration avec Pierre Alliez (Geometrica), et Denis Zorin (NYU).

• 24-31 Mai 2006 : Séjour d'Herve Bronnimann à Sophia Antipolis.

  Travail sur la proposition de standardisation d'arithmetique d'intervalles en C++.

  Egalement, visite d'Herve et Sylvain le 31 Mai a l'ENS Lyon pour travailler avec Guillaume Melquiond.

• 30 Mars 2006 : Soutenance de these de Zilin Du a NYU.

  Sylvain Pion (en video-conference) et Herve Bronnimann sont membres du jury.

• 6-10 Fevrier 2006 : Séjour de Zilin Du (NYU) d'une semaine à Sophia Antipolis.

  Travail avec Z. Du sur l'évolution de la bibliothèque CORE.

• 2 Fevrier 2006 : Le programme REUSSI entre la NSF et l'INRIA a ete accepte, avec GENEPI comme l'une des equipes associees participantes.

  Des sejours d'etudiants de NYU seront donc attendus pour l'ete 2006.

• 8-14 Octobre 2005 : Séjour de Sylvain Pion d'une semaine à New York.

  Travail avec C. Yap sur l'évolution de la bibliothèque CORE, ansi que sur les opérations certifiées sur les courbes. Également avec H. Brönnimann sur les concepts et l'arithmétique d'intervalle en C++.

• 3-8 Octobre 2005 : Sylvain Pion et Hervé Brönnimann vont au meeting de standardisation C++ à Mont-Tremblant, Canada.

  Présentation de la proposition d'arithmétique d'intervalles dans la bibliothèque standard C++.

• 1-30 Juin 2005 : Séjour de Hervé Brönnimann à Sophia Antipolis.

  Travail sur la proposition d'ajout d'arithmétique d'intervalles dans le standard C++, ainsi que sur les concepts géométriques.

• 22 Avril - 15 Mai 2005 : Séjour de Sylvain Pion et Monique Teillaud à New York.

  Travail sur les algorithmes d'intersection de courbes algébriques.
  Travail sur les perturbations symboliques pour les algorithmes géométriques.

  Monique Teillaud a donné deux exposés:
  - introduction à la bibliothèque CGAL, dans le cadre d'un cours de Chee Yap.
  - perturbations symboliques pour les triangulations de Delaunay 3D, dans le cadre du Theory Seminar du Courant Institute.

• 25-28 Octobre 2004 : Séjour de Guillaume Melquiond (doctorant de l'ENS Lyon, co-auteur de S. Pion et H. Brönnimann) à l'INRIA Sophia Antipolis.

  Travail sur les preuves formelles de filtres arithmétiques utilisés dans les prédicats géométriques.
  Guillaume a donné un exposé intitulé "Génération de bornes certifiées pour les valeurs et les erreurs d'arrondi."

• 22-27 Octobre 2004 : Séjour d'Hervé Brönnimann et Jon Lenchner (étudiant) à l'INRIA Sophia Antipolis.

  Travail sur les concept checkers pour le noyau géométrique de CGAL.
  Hervé a donné un exposé intitulé "Algorithm Engineering for Geometric Algorithms".

• 16-20 Août 2004 : Séjour de Chee Yap (New York University) à l'INRIA Sophia Antipolis.

  Outils algébriques pour les problèmes géométriques, et approximations certifiées de courbes. Discussions sur la réalisation d'un noyau algébrique basé sur CORE, pouvant s'interfacer avec le noyau courbe de CGAL (en cours de développement). Et travaux sur des papiers en cours.
  Chee a donné deux exposés intitulés "Complete Subdivision Algorithm for Intersecting Bezier Curves" et "Shortest Path amidst Disc Obstacles is Computable".

• 7-25 Juin 2004 : Séjour de Sylvain Pion à New York.

  Conférence SoCG et CGAL User workshop.
  Workshop de lancement de Genepi, cf ci-dessous.
  Travail sur les concept checkers pour le noyau géométrique de CGAL.

• 14-18 Juin 2004 : Mini-workshop d'une semaine à New York, juste après la conférence SoCG et le CGAL User Workshop.

  Participants INRIA : Sylvain Pion, Monique Teillaud, Mariette Yvinec. (liste complète sur la page du workshop)

Programme de travail

• Programmation générique et noyau géométrique.
• Robustesse
• Structures de données.

Pour en savoir plus....

Échanges de chercheurs prévus initialement

Nous prévoyons deux à trois échanges trans-atlantiques par an, avec une durée de séjour entre deux et quatre semaines (Juin 2004, NYC; Octobre 2004, INRIA; Mars 2005, INRIA; Juin/Juillet 2005, NYC; Octobre 2005, INRIA). Ci-dessous le détail des prévisions pour 2004 :

Accueil de chercheurs	Missions INRIA
Octobre 2004 : Visite de deux semaines de H. Brönnimann à l'INRIA, courant Octobre 2004 (lors des vacances d'Automne de Polytechnic University). Accompagné éventuellement d'un étudiant Américain en thèse (junior) qui resterait pour une durée allant jusqu'à quatre semaines pour avancer le projet discuté, dans un encadrement INRIA. Davantage de visites sont prévues pour 2005, en mars et octobre.	Juin 2004: À l'occasion de la conférence ACM de Géométrie Algorithmique, organisée par H. Brönnimann, visite et séjour de deux semaines par des membres INRIA (dont S. Pion, M. Yvinec, M. Teillaud).   Juin/Juillet 2004: Visite longue d'un membre junior de GEOMETRICA à New York, pour une durée de un mois.

Prévisions pour l'année 2005 : ici.

Réunions, workshops, etc.

Juin 2004 :

À l'occasion de la conférence ACM de Géométrie Algorithmique (SoCG), organisée par H. Brönnimann, organisation d'un atelier des utilisateurs et développeurs de CGAL, co-organisé par des membres de GEOMETRICA. Participation forte des partenaires.

Impact

• sur la collaboration déjà existante avec votre partenaire

Le retour de S. Pion en temps que CR dans GEOMETRICA est l'occasion de renouer de manière solide des collaborations entre GEOMETRICA et l'équipe de H. Brönnimann d'une part, et celle de C. Yap d'autre part.

Un autre aspect important de cette collaboration est la diffusion de CGAL outre atlantique, via l'échange d'étudiants et de réunions de travail.

• sur la collaboration avec d'autres projets INRIA

Les questions algébriques liées aux manipulations de courbes mentionnées précédemment impliqueront une collaboration avec des membres du projet GALAAD (M. Teillaud).

• sur la collaboration avec d'autres équipes de l'organisme étranger partenaire

Sur ces mêmes questions d'objets courbes, nous comptons également collaborer (comme par le passé [4]) avec I. Emiris de l'université d'Athènes.

Historique de la collaboration

Divers

Bibliographie

1

J.-D. Boissonnat and M. Yvinec, traduction H. Brönnimann, Algorithmic Geometry, Cambridge University Press, January 1998, 520 pages, 191 exercices.

2

The Boost Interval Arithmetic Library: acceptée après examen public approfondi dans la bibliothèque Boost (www.boost.org). Avec S. Pion (post-doc) and G. Melquiond (étudiant). 8500 lignes de code.

3

H. Brönnimann, C. Burnikel et S. Pion, "Interval arithmetic yields efficient arithmetic filters for computational geometry,'' Discrete Applied Mathematics, 109:25-47, 2001.

4

H. Brönnimann, I. Emiris, V. Pan et S. Pion, "Sign Detection in Residue Number Systems,'' Theoret. Computer Science, Special Issue on Real Numbers and Computers (210), 1999, 173-197.

5

H. Brönnimann, L. Kettner, S. Schirra and R. Veltkamp, "Application of the Generic Programming Paradigm in the Design of CGAL," dans Lecture Notes in Computer Science (LNCS 1766), M. Jazayeri, R. G. K. Loos, D. R. Musser (Eds.), Springer Verlag, pp. 206-217, 2000.

6

H. Brönnimann, G. Melquiond, and S. Pion, "The Boost interval arithmetic library,'' Proc. 5th conference on Real Numbers and Computer, September 2003.

7

H. Brönnimann et S. Pion, "Exact rounding for geometric constructions,'' Abstracts Symposium on Scientific Computing, Computer Arithm. and Validated Numerics (SCAN), pp. XIII:1-XIII:5, 1997.

8

H. Brönnimann et M. Yvinec, "A complete analysis of Clarkson's algorithm for safe determinant evaluation,'' Rapport de Recherche 3051, INRIA, 1996.

9

H. Brönnimann et M. Yvinec,"Efficient Exact Evaluation of Signs of Determinant,'' Algorithmica 27:21-56, 2000.

10

S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel, "An adaptable and extensible geometry kernel,'' In Proc. Workshop on Algorithm Engineering, volume 2141 of Lecture Notes Comput. Sci., pages 79-90. Springer-Verlag, 2001.

Notes

...CGAL

CGAL : Computational Geometry Algorithms Library, bibliothèque C++ Open Source à laquelle participe GEOMETRICA. http://www.cgal.org