exo7 7250

Un diagramme de Voronoï est une famille de parties du plan (ou de l’espace, mais dans cet exercice on se limitera au plan) et de points associés telle que:

• chaque partie du plan a un unique point associé, qui est contenu dedans;

• chaque partie est exactement égale à l’ensemble des points du plan qui sont plus proches du point associé à cette partie que des points associés aux autres parties.

Autrement dit, c’est une famille $(A_i, P_i)_{i \in I}$, où:

• $I$ est un ensemble;

• pour tout $i \in I$, $A_i$ est une partie (i.e. un sous-ensemble) du plan et $P_i \in A_i$;

• pour tout $i \in I$, on a (en notant $\mathcal{P}$ le plan): $$A_i = \left\{ \; Q \in \mathcal{P} \; \middle/ \; \forall j \in I \setminus \{i\} \; P_iQ \leq P_jQ \; \right\}.$$

Les parties $A_i$ sont appelées les cellules du diagramme de Voronoï. Le point $P_i$ associé à la cellule $A_i$ est appelé le germe de la cellule.

Les diagrammes de Voronoï sont un outil utile pour représenter les zones de couverture d’antennes radio, ou pour étudier l’implantation d’écoles, d’hôpitaux, de bureaux de poste, etc, dans une région.