GENEPI : Equipe associée - INRIA

EQUIPE ASSOCIEE	GENEPI
sélectionnée en	2004

Projet INRIA : GEOMETRICA Organisme étranger partenaire 1 : Polytechnic University Brooklyn Organisme étranger partenaire 2 : New York University

Unité de recherche INRIA : Sophia Antipolis
Thème INRIA : Sym B Pays : États-Unis Pays : États-Unis

Coordinateur français

Coordinateur étranger 1

Coordinateur étranger 2

Nom, prénom Pion, Sylvain Brönnimann, Hervé Yap, Chee

Grade/statut Chargé de recherche Assistant professor Professor

Organisme d'appartenance
INRIA Sophia Antipolis, Projet GEOMETRICA Polytechnic University Brooklyn, Computer and Information Science Department Courant Institute of Mathematical Sciences, New York University

Adresse postale 2004 Route des Lucioles - BP 93 FR-06902 Sophia Antipolis 6 MetroTech Center Brooklyn, NY 11201, New York, USA 251 Mercer Street, New York, NY 10012, New York, USA

URL http://www-sop.inria.fr/geometrica/collaborations/genepi/ http://geometry.poly.edu/genepi/ http://www.cs.nyu.edu/cs/faculty/yap/

Téléphone +33 4 92 38 50 25 +01 (718) 260 3538 +01 (212) 998 3115

Télécopie +33 4 92 38 76 43 +01 (718) 260 3609 +01 (212) 995 4121

Courriel Sylvain.Pion@sophia.inria.fr hbr@poly.edu yap@cs.nyu.edu

La proposition en bref

Mots-clés : Generic geometric algorithms, generic interfaces to graph data structures, geometric kernels, curved objects, non-robustness issues, CGAL

Thématique de la collaboration : Our work is centered on various problems that arise during the implementation of computational geometric algorithms : the genericity aspects of algorithms, and the robustness aspects. These research themes are heavily connected to the work on CGAL.

Generic programming of geometric algorithms : interfaces to the geometry and to the data structures. (collaboration mostly with H. Brönnimann) The first kind of problems is linked to the definition of interfaces (APIs) between the combinatorial and central parts of algorithms and the geometric objects that they manipulate. In order to have generic and re-usable implementations of such algorithms, we parameterize them by kernels which provide the geometry part. The problems that we work on are the definitions of the mathematical concepts corresponding to the different categories of geometry that each algorithm can handle. The goals here are to try to maximize the usability of generic algorithms, and to introduce concepts that facilitate their documentation.
The other aspect of genericity is the interface between the concrete memory storage of the data structures (such as polyhedral surfaces, triangulations...), and the algorithms that manipulate them (point location, meshers...). The idea here is to be able to apply generic algorithms on different concrete data structures providing a common interface. We plan to extend the work done by H. Brönnimann on the Halfedge Data Structure and in the Boost Graph Library to the structures of interest to CGAL, namely the 2D-3D triangulations and simplicial complexes.

Robust handling of curved objects. (collaboration mostly with C. Yap) The second aspect of the work concerns the non-robustness issues that are well-known to cause problems to computational geometry algorithms. In the past, we have developed several methods to handle these issues, and we plan to extend them to curved objects, beginning with low degree algebraic objects. More specifically, we plan to investigate the use of algebraic techniques introduced in the CORE library, and interface it with the CGAL curved kernel currently under development. A somewhat new direction in our collaboration is to address the numerical/parametric view of algebraic curves and surfaces. Until now, researchers in computational geometry have emphasized the purely algebraic view of curves and surfaces. But in practice, the numerical/parametric view is dominant. However the robustness issues here are mostly open. A new paper by one of the participants (Yap) has started to open up this line of investigation.

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 this year 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, 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 with other people like I. Emiris, from the University of Athens. With the arrival of Jon Lenchner, we are further investigating a possible collaboration with the computer graphics team at IBM Research.

II. BILAN 2004

The assessment of this first year of the associated team is overall positive. We have performed almost all planned exchanges, with the exception of no student sent to New York, and shorter stays than planned. The budget showing only 55% of use, is mostly due to the unexpectedly cheap accomodations that we found in New York ($30 per night instead of 110€ planned). We also note an unbalanced situation between the exchanges from and to INRIA, since our partner's team is less numerous. For the following years, we plan to improve the situation by including C. Yap's group (New York University) within the associated team (this was not an option for the first year since he was on sabbatical).

Rapport scientifique pour l'année 2004

In june, we have organized a mini-workshop in Poly, around the themes of GENEPI, with 3 senior INRIA researchers attending. Twelve people attended this workshop, which was conveniently co-located with the ACM conference SoCG (also organized by H. Brönnimann). At this workshop, we decided to first focus on the work around concepts of geometry, that is, the link between generic geometric algorithms, and the different sets of geometric primitives they can use. This work is now converging towards a contribution to CGAL. More details on the topics discussed at the workshop can be found on this dedicated web page.

In august, we have invited C. Yap at INRIA, to start a collaboration around curved objects, with M. Teillaud. One of the main goals of this collaboration is to allow the interfacing between the CORE library of algebraic numbers and the CGAL curved kernel. C. Yap gave two seminars during his stay at INRIA : "Complete Subdivision Algorithm for Intersecting Bezier Curves" and "Shortest Path amidst Disc Obstacles is Computable".

Finally, in october, H. Brönnimann and his student J. Lenchner visited INRIA. Hervé gave a seminar entitled "Algorithm Engineering for Geometric Algorithms". We worked on several topics during their stays :

H. Brönnimann and S. Pion have continued the work on concepts of geometries. From the point of view of the code development, we have collaborated within CGAL and the code for concept checking is now written for the CGAL Kernel and Triangulation packages. This already identified several inconsistencies and enriched the documentation. We are currently working on developing concept checking with other packages. H. Brönnimann and K. Amisial have been working on the generic algorithms for manipulation of planar subdivisions (HDSTL) and on providing a per concept interface with the CGAL halfedge data structure to enable those generic algorithms to work on the CGAL data structure as well, and will be releasing their work within a few months.
J. Lenchner and O. Devillers developed an algorithm that finds an ordinary point in an arrangement of not all parallel, not all coincident lines in the plane in time O(n log n). The existence of such a point was guaranteed by a recent theorem of Lenchner's that also gave a lower bound on the number of such points. H. Brönnimann and J. Lenchner also work on the related problem of the Dirac and Motzkin conjecture.
G. Melquiond from INRIA-ARENAIRE also visited us at the same time. He gave a seminar entitled "Génération de bornes certifiées pour les valeurs et les erreurs d'arrondi". He worked with S. Pion on a problem related to the robust implementation of geometric algorithms, namely, the problem of formal proofs of arithmetic semi-static filters. This technique is used to implement efficient and exact geometric predicates, but is quite prone to programming or logic errors, hence can benefit greatly from formal proofs techniques. This work is having consequences on the CGAL kernel which implements those filters. An article is also submitted to a conference on this work.

Bilan des échanges effectués en 2004

III. PREVISIONS 2005

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 2005 continues what was begun in 2004 for some parts, and extends it with the collaboration with C. Yap.

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.
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, together with our students A. Mebarki and J. Lenchner. 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 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.

Nom	statut	provenance	destination	objet	durée (en semaines)
Pion	CR	INRIA Sophia	Polytechnic U. Brooklyn	Conference, workshop, visit	3
Teillaud	CR	INRIA Sophia	Polytechnic U. Brooklyn	Conference, workshop	2
Yvinec	CR	INRIA Sophia	Polytechnic U. Brooklyn	Conference, workshop	2
Yap	Professor	NYU (via MPI, Saarbücken)	INRIA Sophia	Visit	1
Brönnimann	Assistant professor	Polytechnic U. Brooklyn	INRIA Sophia	Visit	1

Nom	statut	provenance	destination	objet	durée (en mois)
Lenchner	Ph.D student	Polytechnic U. Brooklyn	INRIA Sophia	Visit	0.25
Melquiond	Ph.D Student	ENS Lyon, INRIA Arenaire	INRIA Sophia	Visit	0.25

Programme INRIA "Equipes Associées"

I. DEFINITION

Présentation de l'Équipe Associée

II. BILAN 2004

Rapport scientifique pour l'année 2004

Bilan des échanges effectués en 2004

III. PREVISIONS 2005

Programme de travail

Budget prévisionnel 2005

Projet INRIA : GEOMETRICA	Organisme étranger partenaire 1 : Polytechnic University Brooklyn	Organisme étranger partenaire 2 : New York University
Unité de recherche INRIA : Sophia Antipolis Thème INRIA : Sym B	Pays : États-Unis	Pays : États-Unis

	Coordinateur français	Coordinateur étranger 1	Coordinateur étranger 2
Nom, prénom	Pion, Sylvain	Brönnimann, Hervé	Yap, Chee
Grade/statut	Chargé de recherche	Assistant professor	Professor
Organisme d'appartenance	INRIA Sophia Antipolis, Projet GEOMETRICA	Polytechnic University Brooklyn, Computer and Information Science Department	Courant Institute of Mathematical Sciences, New York University
Adresse postale	2004 Route des Lucioles - BP 93 FR-06902 Sophia Antipolis	6 MetroTech Center Brooklyn, NY 11201, New York, USA	251 Mercer Street, New York, NY 10012, New York, USA
URL	http://www-sop.inria.fr/geometrica/collaborations/genepi/	http://geometry.poly.edu/genepi/	http://www.cs.nyu.edu/cs/faculty/yap/
Téléphone	+33 4 92 38 50 25	+01 (718) 260 3538	+01 (212) 998 3115
Télécopie	+33 4 92 38 76 43	+01 (718) 260 3609	+01 (212) 995 4121
Courriel	Sylvain.Pion@sophia.inria.fr	hbr@poly.edu	yap@cs.nyu.edu