Contract type : Public service fixed-term contract
Level of qualifications required : Graduate degree or equivalent
Fonction : PhD Position
Context and motivation
Geometric problems are central in many areas of science and engineering. Computational geometry, the study of combinatorial and algorithmic problems in a geometric setting, has tremendous practical applications. Traditionally, the scope of computational geometry has been limited to algorithms on data in the Euclidean space.
However, some results in computer science used combinatorial hyperbolic structures [SST,DL]. Also, hyperbolic surfaces are natural and appear in various fields in physics and material sciences. For instance, the triply periodic minimal surfaces of R3 are hyperbolic.
We have already obtained results about the computation of Delaunay triangulations in hyperbolic spaces [BDT] and on very specific hyperbolic surfaces [IT]. The need of a geometric toolbox for hyperbolic surfaces has become critical to tackle more general hyperbolic surfaces. Some combinatorial constructions on such surfaces have been proposed from a mathematical point of view [Bus]; however the algorithmic and practical properties have hardly been studied.
The purpose of this PhD is to explore the geometry of hyperbolic surfaces and provide such a geometric toolbox.
Two main discrete structures have been proposed to describe hyperbolic surfaces: Fenchel-Nielsen coordinates and fundamental polygon with side gluings. These representations are not unique, which leads to research question like: how to compute a good pants decomposition? or how to compute a fundamental domain that is a Voronoi cell? Also, elementary queries associated to the underlying surface can be studied in both situations. A typical question that is both extremely useful and a deep research question is: how to calculate the distance between two given points on an hyperbolic surface?
Many other interesting questions may be considered, so, the candidate will have the opportunity to choose between different possible directions. In each case, the goal will be to present an algorithm, analyze it, and implement it. Considering the potential applications and targeted users, SageMath seems to be a good option for implementations.
[BDT] Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Journal of Computational Geometry. 5(2014)
[Bus] Peter Buser. Geometry and spectra of compact Riemann surfaces. Springer Science & Business Media, 2010.
[DL] Vincent Despré and Francis Lazarus. Computing the geometric intersection number of curves. 33rd International Symposium on Computational Geometry (SoCG 2017).
[IT] Iordan Iordanov and Monique Teillaud. Implementing Delaunay triangulations of the Bolza surface. 33rd International Symposium on Computational Geometry (SoCG 2017).
[STT] Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. Journal of the American Mathematical Society. 1(1988).
This PhD thesis involves knowledge from both
- mathematics (in particular: low-dimensional topology and geometry)
- and computer science (in particular: algorithms, graph theory, and C++/Python).
Candidates should have a strong expertise in one of those fields and a real interest for the other one.
French is no compulsory.
English is required.
- Subsidized meals
- Partial reimbursement of public transport costs
- Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
- Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
- Professional equipment available (videoconferencing, loan of computer equipment, etc.)
- Social, cultural and sports events and activities
- Access to vocational training
- Social security coverage
Salary: 1982€ gross/month for 1st and 2nd year. 2085€ gross/month for 3rd year.
Monthly salary after taxes : around 1596,05€ for 1st and 2nd year. 1678,99€ for 3rd year. (medical insurance included).
- Theme/Domain : Algorithmics, Computer Algebra and Cryptology
- Town/city : Villers-lès-Nancy
- Inria Center : CRI Nancy - Grand Est
- Starting date : 2020-10-01
- Duration of contract : 2 years
- Deadline to apply : 2019-05-01
The keys to success
May 1st, 2019 (Midnight, Paris time)
How to apply
- Upload your file on jobs.inria.fr in a single pdf or zip file
- And send your file to the two advisors.
Your file should contain the following documents:
- Your CV.
- A cover letter describing your interest in this topic.
- A short (max one page) description of your Master thesis (or equivalent) or of the work in progress if not yet completed.
- Your degree certificates and transcripts for Bachelor and Master (or the last 5 years).
- Master thesis (or equivalent) if it is already completed and publications, if any (it is not expected that you have any). Only the web links to these documents are preferable, if possible.
- In addition, one recommendation letter from the person who supervises(d) your Master thesis (or research project or internship) should be sent directly by its author to the advisors.
Applications are to be sent as soon as possible.
Inria, the French national research institute for the digital sciences, promotes scientific excellence and technology transfer to maximise its impact. It employs 2,400 people. Its 200 agile project teams, generally with academic partners, involve more than 3,000 scientists in meeting the challenges of computer science and mathematics, often at the interface of other disciplines. Inria works with many companies and has assisted in the creation of over 160 startups. It strives to meet the challenges of the digital transformation of science, society and the economy.
Instruction to apply
Defence Security :
This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment.
Recruitment Policy :
As part of its diversity policy, all Inria positions are accessible to people with disabilities.
Warning : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed.