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)

Partenaire français

GEOMETRICA - INRIA Sophia-Antipolis
2004 route des Lucioles - BP 93 - 06902 Sophia Antipolis
Responsable de l'équipe : Jean-Daniel Boissonnat
Participants : Sylvain Pion, Monique Teillaud, Christophe Delage, Pierre Alliez, Mariette Yvinec
 

Partenaires étrangers

New York University,
251 Mercer Street, NY 10012, New York, USA.
Responsable de l'équipe : Chee Yap
Participants : Chris Wu, Jeff Lindy, Dave Millman, Jihun Yu

 

Polytechnic University Brooklyn,
6 MetroTech Center, Brooklyn, NY 11201, USA.
Responsable de l'équipe : Hervé Brönnimann
Participant : Jon Lenchner

Evénements


Programme de travail

Le travail envisagé consiste en l'étude et le développement d'algorithmes génériques et robustes pour la manipulation d'objets géométriques, en particulier les objets courbes, ainsi que le développement des interfaces des structures de données (graphes) supportant les objets géométriques.

Nous développons ces points :

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

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.

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 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

Contact : Sylvain Pion