Votre courriel/e-mail of the proposer : Monique.Teillaud@sophia.inria.fr

Nom du projet/Research team name : Geometrica

Unité de recherche/Research Unit : Sophia-Antipolis

Thème INRIA/Research theme : Sym

Nom et prénom du chef de projet/Research team leader name : Jean-Daniel Boissonnat

Encadrant du stage/Intern tutor : Monique Teillaud

Titre du sujet du stage/Topic of the Internship:

CGAL Curved Kernel

Type de stage/Intern level : Mastère-Master's thesis

Durée minimum du stage (en mois)/Internship duration (months) : 4

Ce stage pourrait-il déboucher sur une thèse ou un post-doc ?/Possibility of a follow-up Ph.D or post-doc : oui-yes

Description du sujet du stage/Internship description (une dizaine de lignes/about ten lines) :

Extending geometric algorithms to the case of curved objects is currently a very active research topic. This was at the heart of the European project ECG and is central again in the following project ACS. There are numerous and various applications, ranging from molecular biology to integrated circuits design, computer aided manufacturing, geographic information systems. One aspect of this research is the study of basic primitives for manipulating conic arcs in the plane, that will be used by various algorithms, for instance construction of arrangements. A kernel for circular arcs is in progress for the CGAL library. The concrete objective of this internship is to extend this kernel to the case of conic arcs. This topic lies at the point where mathematics and computer science converge: - geometry, and manipulation of unbounded arcs: how to represent them? how to manipulate intersections at infinity? (projective space?), - geometric filtering (bounding boxes, bounding polygons), - arithmetic aspects, - algebraic aspects, with the manipulation of algebraic numbers, - programming and experimentation in CGAL. This research is related with several collaborations, in particular within the Arcadia ARC and the European project ACS. To know more: CGAL curved kernel Open Source Project CGAL Introduction to CGAL

Préciser les pré-requis nécessaires pour ce stage/Prerequisites :

Knowledge of Computational Geometry, data structures, complexity analysis. Taste and knowledge in geometry and mathematics in general. Knowledge of C++ and STL. Taste for code of good quality.