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

Rapport scientifique pour l'année 2006

The work during the year has been organized around several visits : Z. Du in Sophia to prepare a paper (to be submitted to SoCG in december) on the re-design of the CORE library for exact algebraic computations ; H. Brönnimann in Sophia in May to polish a revision of our proposal for standardization of interval arithmetic in C++ ; J. Yu, C. Wu and D. Milmann visiting Sophia for longer internship stays working respectively on the topics of the CORE library (collaboration with S. Pion), meshing algorithms (mostly with P. Alliez) and predicates for the Voronoi diagram of circles (mostly with C. Delage). Finally, S. Pion stayed in New-York for one week in October for finalizing the paper submission to SoCG.

H. Brönnimann has started working at Bloomberg for one year since september, hence the collaboration will be slowed down during this period. Together with G. Melquiond of ARENAIRE, we have further worked on our proposal for standardization of interval arithmetic in the C++ standard library, and we have issued a first revision and working on a second, 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.

With C. Yap, several questions around robustness issues have been discussed. With Z. Du finishing his PhD. thesis (S. Pion and H. Bronnimann were members of the jury), a younger Ph.D. student had to be trained for working on the CORE library (J. Yu), which he did in his summer stay at Sophia. One of his tasks is to try to couple CORE with some algorithms in CGAL needing algebraic computations.

Research work on these 3 years was spanned over many aspects connected to the robust, efficient and adaptable implementation of geometric algorithms. CGAL has played a central role here.

We have first worked on concept of geometries for a better specification of generic geometric algorithms. A tentative implementation has been realized with CGAL based on the Boost concept checkers, but a released implementation will probably have to wait for the introduction of proper concepts in the C++ language (the next standard is in preparation). Another subject that we have been working on is a proposal for the standardization of interval arithmetic in C++. This required to go deep in the semantic of interval arithmetic and gathering the opinion of interval experts. Interval arithmetic is a fundamental tool used in our case to ensure the exactness of the evaluation of geometric predicates. This work has been done mostly in collaboration with Herve Bronnimann and Guillaume Melquiond (Arenaire).

Another topic that we have worked on is the improvements of geometric predicates used in the computation of Voronoi diagrams of ellipses, with David Milmann and Christophe Delage. Namely the arithmetic degree has been increased, as well as the number of needed arithmetic operations.

Finally, we worked on the redesign of the CORE library, a library of exact algebraic computations used by several geometric algorithms. The goal here has been to make more extensible and efficient by adopting a generic design. This work has been done mostly in collaboration with Chee K. Yap, Zilin Du and Jihun Yu, as well as Herve Bronnimann for parts of it, and it should lead to a paper submission to SoCG 2007. Some ongoing discussions about general schemes for symbolic perturbations have also taken place, and we hope that some general technique could be made available for CGAL, if we find an efficient and general enough one.

Rapport financier 2006

Bilan des échanges effectués en 2006

1. Seniors

2. Juniors

III. PREVISIONS 2007

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. The planned work for 2007 is mostly a continuation of what was already started.

Generic programming of geometric algorithms. We will continue the work concerning the concepts of geometries used by the various algorithms in CGAL. The impact of this work is the ability to broaden the applicability of existing algorithms, both within CGAL (promoting internal reuse) and to more application domains.
From the implementation point of view, we have introduced concept checkers in CGAL, which are a way to statically check the validity of template parameters against the requirements expressed as concepts. These enforce requirements on parameter classes and make the code both more robust (errors are detected immediately) and easier to design (since documentation concepts now translate into code entities). Currently, concept checking is provided for several key packages (kernel, triangulations). We will continue to extend concept checking to all of CGAL, and work on unifying concepts and eliminating functional duplication between packages. This work follows in parallel the effort of standardization which is done on language-level concepts in C++ (by Gregor, Stroustrup et al).
One example we plan on zooming in is triangulation data structures. Those structures, also known as simplicial complexes, are currently present in at least three forms in CGAL. We plan on unifying those through a separate simplicial complex library. We are also going to work on generic interfaces for the operations on simplicial complexes, task which we plan to work on with a student. The idea is to devise an interface that decouples the algorithms acting on such complexes. Currently, the algorithms are part of the triangulation class and hence not easily reusable. Extracting them as stand-alone algorithms would allow their independent reuse and provide more genericity in CGAL. The challenge is to design the interface so that this can be done.
Another goal of this work is to allow several representations of these data structures in memory, which is part of A. Mebarki's Ph.D thesis subject, with the algorithms operating generically on every single one of them (again promoting internal code reuse). Along with straightforward applications to CGAL, we are targeting specific applications of simplicial complexes.

Robust handling of curved objects. Our work goes towards answering the growing need for the robust and efficient manipulation of curved objects in numerous applications. The CGAL kernel currently provides several functionalities which are, however, mostly restricted to linear objects. We would like to continue the work on the extension to curved objects. More specifically, we would like to interface it with the CORE library developped by C. Yap's team, which provides algebraic primitives. First target applications are the implementations of the predicates necessary to compute arrangements of conic arcs, and possibly Voronoi diagram of complex objects involving conic arcs. The work involved here concerns the efficient and exact handling of algebraic numbers and systems.
Most practical techniques in curves and surfaces are parametric curves and surfaces (e.g. Bezier patches). Here, the current techniques are numerically-based and they suffer from inexactness and nonrobustness. To solve this problem from the exact geometric computation (EGC) viewpoint, we need to understand root bounds and to apply them carefully in our algorithms. This work has begun in a new paper of one of the participants (Yap), but it is clear that many issues remain.

On the implementation side, we plan to continue the design work on our proposal to standardize interval arithmetic in C++ (work with H. Brönnimann). On the other side, we plan to work on multiple precision issues and revisit the implementation of the CORE library, whose quality and efficiency can be improved in some respects, this work might be based on the libraries MPFR and MPFI developed at INRIA (in SPACES and ARENAIRE).

Budget prévisionnel 2007

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 2 stays of 1 week in New York.

© INRIA - mise à jour le 20/10/2006