PhD proposal: Simulation of random geometric structures


Olivier Devillers (


Gamble, Loria and INRIA Nancy Grand-Est.


The complexity of geometric algorithms is often express in terms of the input size and sometimes of the output size, but the behavior of these algorithms may depend drastically on the geometric distribution of the input. The difference between the best-case and the worst-case can be important. An alternative is to analyze these algorithms under the hypothesis of a probabilistic distribution of the data. When the input is a point set, an easy probabilistic hypothesis is to consider that points are independently distributed under some law (Poisson distribution, uniform distribution. . . ), unfortunately this hypothesis of indepen- dance may be unsuitable for several applications.
The use of non independent distribution is very difficult to analyze theo- retically, thus having access to simulations of practical instances would be of tremendous help to guide the intuition and to lead to reasonable conjectures. Unfortunately, the generation of useful random instances is a difficult question in itself. We plan to attack three specific questions, as described below: simulation of geometric structures, of conditioned structures, and of dependent pointsets.

Project description

The goal of this research is to design and realize tools for the generation of several random geometric objects. These tools will be used to benchmark geometric algorithms and to establish new probability conjectures.

The detailed description of the PhD proposal can be downloaded from here.

Required qualifications

mathematical aspects (probability),  algorithmic aspects,  C++ (templates, etc)

General information

  • Duration: 3 years.
  • Starting date: 1st October 2018

How to apply

Send the following documents to in a single ZIP file:

  • CV.
  • A motivation letter describing your interest in this topic.
  • Your degree certificates and transcripts for Bachelor and
    Master (or the last 5 years if not applicable).
  • Master thesis (or equivalent) if it is already completed, or a
    description of the work in progress, otherwise.
  • Publications, if any (it is not expected that you have any).

In addition, at least one recommendation letter from the person who supervises(d) your Master thesis (or research project or  internship) should be sent. At most two other recommendation  letters may be sent. The recommendation letter(s) should be sent  directly by their author to

Help and benefits

  • Monthly net salary of 1600 €. Medical insurance included.
  • Possibility of free French courses.
  • Help for finding housing.
  • Help for the resident card procedure and for husband/wife visa.
  • Lunch cost at INRIA is 2,78 €.

Logo du CNRS

Logo d'Inria

Logo Université de Lorraine