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 2005

Rapport scientifique pour l'année 2005

The work during the year has been organized around 3 visits : S. Pion and M. Teillaud in New York in April, then H. Brönnimann in Sophia in June, and then S. Pion in New York again in October, together with a joint visit with H. Brönnimann in Canada for a C++ standardization meeting.

The work with H. Brönnimann has been focused on two things : the continuation of the work on concepts for the implementation of generic geometric algorithms, still aimed at an integration in CGAL in the near future. But more timely, we have worked on a proposal for standardization of interval arithmetic in the C++ standard library (with G. Melquiond of ARENAIRE), which is a follow-up of our common work on the Boost interval library. This work has been presented in front of the C++ standardization committee, and is currently in the process of a revision for a final submission in 2006.

With C. Yap, several questions around robustness issues have been discussed, such as the certified approximation of curved objects by polygonal approximations, including certified intersection of curves, or the generalization of the various symbolic perturbation schemes that are used in several geometric algorithms. M. Teillaud gave 2 talks at NYU during our visit : a first introduction to CGAL, and a talk on symbolic perturbations for vertex removal in 3D triangulations. Other topics such as interfacing the CORE library developed at NYU (which provides exact algebraic numbers), with the CGAL curved kernel, are still waiting for the curved kernel to be more mature.

“A proposal to add interval arithmetic to the C++ Standard Library”, by H. Brönnimann, G. Melquiond, S. Pion, ISO Document Number N1843=05-0103, July 2005.

Rapport financier 2005

Bilan des échanges effectués en 2005

1. Seniors

2. Juniors

III. PREVISIONS 2006

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 2006 is mostly a continuation of what was begun in 2004 and 2005.

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

1. Co-financement

This collaboration does not already benefit from funding from INRIA or our partners nor any other institution.

We are looking for additional funding from our partner and other sources.

Concerning the first partner : we are looking for some funding from several sources : an Othmer Junior Faculty Fellow grant that H. Brönnimann has received. And we are asking some funding from the NSF as well.

Concerning the second partner : our collaborators at NYU are planning to submit a new proposal for international collaboration to the NSF for this joint work, with the possibility of long term exchange of students. Moreover, C. Yap is able to dedicate $1000 in this collaboration from his research grant.

2. Echanges

Planned visits from New York to Sophia Antipolis :

• C. Yap (senior) plans to come 2 weeks in the summer.

• Z. Du (junior), a student of C. Yap, plans to visit INRIA 2 weeks in January.

Planned visits from Sophia Antipolis to New York :

• S. Pion (senior) and M. Teillaud (senior) plan to stay 2 weeks in New York.

Other visits :

• S. Pion (senior) plans to go to the Computational Geometry workshop, with H. Brönnimann, at the Barbados, in February,

  followed by one week in New York.

© INRIA - mise à jour le 21/10/2005