Direction des Relations Européennes et Internationales (DREI)

Programme INRIA "Equipes Associées"

I. DEFINITION

La proposition en bref

Présentation de l'Équipe Associée

1. Présentation du coordinateur étranger

Hervé Brönnimann is Assistant Professor at the Polytechnic University Brooklyn, New York, USA. He has published several papers on all aspects of geometric computing in international journals, including on theoretical topics such as derandomization of geometric algorithms (the topic of his Ph.D. thesis) and practical topics as arithmetic filters for geometric computing. He graduated from École Normale Supérieure of Paris before completing his Ph.D. in Computer Science at Princeton University in 1995. He held a permanent research position in the PRISME project at INRIA from 1995 to 1998. His research interests include analysis and design of algorithms, with a focus on geometric algorithms. At INRIA, he was a collaborator in CGAL, where he was involved with maintaining a large portion of the geometry kernel. At Poly, he spearheaded the effort that led to the Boost Interval Arithmetic Library. More recently, he became interested in applying results in deterministic sampling and data stream techniques to data mining and network forensics. Again, he is interested there in theoretically efficient yet highly practical algorithms, and their implementation.

Chee Keng Yap is Professor of Computer Science at the Courant Institute of Mathematical Sciences, New York University. He has published over 130 papers in major conferences and journals, in the area of algorithms and complexity. His research interests include computational geometry, visualization problems, computer algebra, and algorithmic robotics. Since 1993, he has been interested in numerical non-robustness, especially issues at the interface between numerical, algebraic and topological computation. A current project called the Core Library aims to bring robust computation out of the research realm and make it widely accessible to all programmers. Yap was born in Singapore and educated in the Boys' Wing, Royal Military College in Malaysia. He received a double S.B. degree (Math and Comp.Sci.) from MIT in 1975 and a Ph.D. (Comp.Sci.) from Yale in 1980. He served on the editorial boards of SIAM J. of Computing (1985-2002), J. of Symbolic Computation (1988--2003), J. of Computer and System Sciences (1986--), Computational Geometry: Theory and Applications (1990--), Int'l J. of Comp. Geometry and Applications (1990--), and Algorithmica (1992--). His two books are the edited volume Advances in Robotics: Algorithmic and Geometric Issues (Lawrence Erlbaum Associates, Inc, 1987) (co-edited with Jack Schwartz) and Fundamental Problems in Algorithmic Algebra (Oxford University Press, 2000).

2. Historique de la collaboration

• 2.1. entre les équipes :

  H. Brönnimann has been working within the CGAL project, and as such, is co-author of a number of papers with members of GEOMETRICA, as well as CGAL packages (triangulations and kernels). Moreover, Hervé has co-directed the thesis of S. Pion on the subjects of robustness issues. He also translated J.-D. Boissonnat and M. Yvinec's book in English. Collaboration has continued during S. Pion's post-doc stay in New York in 2002 where they co-supervised a student, G. Melquiond, to produce the Boost Interval arithmetic library, which led to publication. Finally, H. Brönnimann is a regular participant of the Journées Françaises de Géométrie Algorithmique, having given courses, on derandomization methods in geometry (1996), on CGAL (1998), and on online geometric algorithms (2003).

  The collaboration with C. Yap is more recent. He worked with S. Pion during his post-doc stay in New York in 2002, on issues related to the CORE library of exact algebraic numbers. Most notably, they improved the separation bounds for common cases of expressions using floating point numbers as input [11]. The collaboration has continued since then, for example by co-editing a special issue of CGTA on robustness issues and writing a survey on exact geometric computation techniques [12].

  Bibliography

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

  2. H. Brönnimann, S. Pion and G. Melquiond. The Boost Interval Arithmetic Library: accepted after thorough public review in the Boost library (www.boost.org).

  3. H. Brönnimann, C. Burnikel and 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 and 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," in 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. Accepted to Theoret. Computer Science, forthcoming Special Issue on Real Numbers and Computers.

  7. H. Brönnimann and 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 and M. Yvinec, "A complete analysis of Clarkson's algorithm for safe determinant evaluation,'' Rapport de Recherche 3051, INRIA, 1996.

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

  10. L. Kettner, K. Mehlhorn, S. Pion, S. Schirra and C. Yap, "Classroom Examples of Robustness Problems in Geometric Computations,'' In Proc. 12th Annual European Symposium on Algorithms (ESA), LNCS vol. 3221, pages 702--713, Springer. Bergen, Norway, September 14 - 17, 2004.

  11. S. Pion, C. Yap, "Constructive Root Bound for k-Ary Rational Input Numbers,'' 19th Annu. ACM Symp. Comput. Geom., San Diego, USA, June 2003.

  12. C. Li, S. Pion, C. Yap, "Recent Progress in Exact Geometric Computation,'' Special issue on the practical development of exact real number computation, Journal of Logic and Algebraic Programming, 2004.

  13. C. Yap, S. Pion, Z. Du and Z. Wang, "Provably Robust Cartesian Volume Meshing,'' Proc. 23rd Army Science Conference, Orlando, Florida, December 2-5, 2002.

  ---

  2.2. entre l'INRIA et l'organisme partenaire :

  Related general pages concerning the scientific relations with the USA : at the DREI (here), and at the DRI of the CNRS (here). And at the french ambassy in the USA.

  Since January 2003, Keith Ross (formerly Prof. Institut Eurecom) has joined Polytechnic University Brooklyn as a full professor. Keith has started several collaborations with Philippe Nain and Eitan Altman. Moreover, Boris Aronov has made several stays at PRISME in the past, without relation with the current associated team.

  Concerning NYU, Ben Goldberg spent a sabbatical year in Rocquencourt, working with Michel Mauny (programming languages), and Denis Shasha spent 2 sabbaticals at INRIA.

3. Impact :

• 3.1.

  The return of S. Pion as researcher in the GEOMETRICA project team is an opportunity to strengthen the links between GEOMETRICA and H. Brönnimann's and C. Yap's groups in the USA. Another aspect of this collaboration is the dissemination of CGAL outside Europe, via students exchanges and work meetings. For instance, H. Brönnimann is proposing several senior thesis topics relying on CGAL for the implementation part. We have several common research topics, and the associated team is definitely an important medium to foster the collaboration.

• 3.2.

  We will collaborate with M. Teillaud, formerly from the GALAAD project-team, on problems related to the geometric treatment of curved objects. Arithmetic issues will also trigger collaborations with M. Daumas and G. Melquiond from ARENAIRE.

• 3.3.

  It is not clear that we will have strong collaborations with other teams of Polytechnic University Brooklyn nor NYU. Nevertheless, we do have several related collaborations on close topics with other people like I. Emiris, from the University of Athens.

II. BILAN 2007

Rapport scientifique pour l'année 2007

The work during the year has been organized around several visits : Jihun Yu (2nd year PhD student of C. Yap) and Dave Milmann (Master student of C. Yap, now starting a PhD at UNC Chapel Hill) visiting Sophia for 2-months internship stays. Jihun Yu worked on the C++ standardization of interval arithmetic, more precisely on providing an implementation of the current proposal, using Boost.Interval and CRLIBM/MPFR (collaboration with Guillaume Melquiond who visited us one week in Sophia). Dave worked on a new topic, namely the parallelization of some algorithms in CGAL. He started with the case of the 3D Delaunay triangulation generation, using OpenMP. The results of both students are excellent, although works remains to be done to complete them. Finally, C. Yap visited us a couple of days in Sophia, where he was part of the HDR jury of Monique Teillaud, and where he was invited to give a talk at the Workshop on Robust Shape Operations (WRSO).

H. Brönnimann continues to work at Bloomberg for another year, hence the collaboration will be slowed down during this period on this side. Together with G. Melquiond of ARENAIRE, we have further worked on our proposal for standardization of interval arithmetic in the C++ standard, and we have issued a second revision and are working on a third, as well as produced a separate proposal specifying the interface for multi-valued logic (named bool_set), which is critical for the use of interval comparisons.

Rapport financier 2007

Bilan des échanges effectués en 2007

1. Seniors

2. Juniors

III. PREVISIONS 2008

Programme de travail

The long term view is that our work is centered on the various problems that arise during the implementation of computational geometric algorithms, especially from the non-robustness point of view, and in the generic programming setting, such as the one found in CGAL. We plan to make significant contributions to CGAL. The two main topics are described in the introduction of this associated team. We now focus more on some topics that arised in studying the robust implementation of geometric algorithms. The planned work for 2008 is mostly a continuation of what was already started. Note that this year corresponds to the third (and probably last) year of the REUSSI program between INRIA and NSF. It is therefore especially important to obtain the funding from the INRIA side to match the US contribution.

Standardization of Interval Arithmetic in C++. We will continue the work on this proposal, since there is strong interest on both sides. C. Yap is interested in having an implementation to be used as part of his CORE library project for exact computing. Note that the interval arithmetic proposal also includes non-algebraic functions, which is something new in the CORE library. This also makes use of the MPFR library developed at INRIA Nancy. We anticipate that a strong moment in 2008 will be connected to the ISO C++ standardization meeting that we are organizing at INRIA in June. We will probably try to dedicate a sub-meeting to this interval arithmetic work.

We will also choose other topics in time, depending on which students are planned to come in the summer. Continuing the work on parallelization of geometric algorithms is a serious candidate, the other one being the study of the impact of the coming concepts (a new language feature) in the next C++ standard on the CGAL kernel.

Budget prévisionnel 2008

1. Co-financement

This collaboration benefits from the REUSSI NSF-INRIA program which provides partial funding for stays of 3 US students at INRIA.

2. Echanges

Planned visits from New York to Sophia Antipolis :

• 3 students of C. Yap, plan to visit INRIA several weeks in the summer.

Planned visits from Sophia Antipolis to New York :

• S. Pion (senior) plans 1 stay of 1 week in New York. Same thing for another senior researcher (probably M. Teillaud).

© INRIA - mise à jour le 19/10/2007