Wiki du LAMA (UMR 5127) - Contributions [fr]

Fichier:Briffod Figure 2.png

2025-05-16T12:28:09Z

Briffod : Briffod a téléversé une nouvelle version de Fichier:Briffod Figure 2.png

Fichier:Figure 1.png

2025-05-16T12:20:47Z

Briffod : Briffod a téléversé une nouvelle version de Fichier:Figure 1.png

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-05-16T12:11:15Z

Briffod : Modification finale

Élève : Briffod Nils

Tuteur : Dorin Bucur

== Introduction ==

Au travers de ce sujet, nous allons réfléchir, réaliser un model mathématique puis le mettre en pratique grâce aux outils informatiques.
Nous parlerons de graphes et d'optimisation de longueurs.

== Problématique ==

En quoi consiste ce problème mathématique relié à un exemple concret ?
Supposons que dans un village où les maisons sont uniformément réparties, un opérateur téléphonique souhaite installer des antennes.
Nous cherchons à minimiser la distance moyenne entre chaque maison et l'antenne 5G.
Autrement dit dans une surface donnée, de forme quelconque, nous devons être capables de trouver les coordonnées optimales du point où l'antenne y sera placée.
Bien que cette question à été simplifiée, elle repose sur un concept mathématique important notamment au sujet de la planification économique.

== Démonstration ==
Comment déterminer le point où la distance moyenne entre la position de l'antenne et tous les autres points de la figure ?

Cette question a été abordée dans un article de recherche par Morgan F. & Bolton R. (2002) publié dans une revue scientifique, [https://www.tandfonline.com/doi/abs/10.1080/00029890.2002.11919849 lien de l'article]

On commence par un modèle très simple : quatre maisons sont positionnées aux sommets d'un rectangle et on va démontrer que la position optimale d'une antenne est au centre du rectangle.
La justification sera donnée par un raisonnement mathématique, basé sur l'analyse de la variation d'une fonction.

Nous sommes dans un rectangle, comme dans la Figure 1.
Nous cherchons a diminuer la somme des longueurs des hypoténuses des deux triangles rectangles (le rouge et le bleu) tout en déplaçant le point A horizontalement.
[[Fichier:Figure_1.png|400px|thumb|center|Figure n° 1]]

Concentrons nous sur les triangles rectangles.
Nous allons déterminer grâce au théorème de Pythagore les longueurs des hypoténuses des triangles:
*Le triangle rectangle <strong style="color:#FF0000">rouge</strong> a pour longueur de coté : <math>x</math>, <math>h</math> et pour hypoténuse : <math>\sqrt{x^2 + h^2}</math>.
*Le triangle rectangle <strong style="color:#0080FF">bleu</strong> a pour longueur de coté : <math>2-x</math>, <math>h</math> et pour hypoténuse : <math>\sqrt{(2-x)^2 + h^2}</math>.

Nous allons faire varier <math>x</math> et observer là où la fonction somme est au minimum.
Définissons notre fonction somme :
<math>f(x) = \sqrt{(2-x)^2 + h^2} + \sqrt{x^2 + h^2}</math>.<br>
Nous allons démontrer que pour tout <math>x</math>, <math>f(x) \geq 2 \sqrt{1^2 + h^2}</math>, avec égalité lorsque <math>x = 1</math>:

On souhaite minimiser <math>f(x)</math>, ce qui revient a chercher quand sa dérivé s'annule.

<math>f'(x) = -\frac{2-x}{\sqrt{(2-x)^2 + h^2}} + \frac{x}{\sqrt{x^2 + h^2}} = 0</math>

<math>\frac{x}{\sqrt{x^2 + h^2}} = \frac{2-x}{\sqrt{(2-x)^2 + h^2}}</math>

<math>\frac{x^2}{x^2 + h^2} = \frac{(2-x)^2}{(2-x)^2 + h^2}</math>

<math>x^2 (2-x)^2 + x^2 h^2 = (2-x)^2 x^2 + (2-x)^2 h^2</math>

<math>x^2 h^2 = (2-x)^2 h^2</math>

<math>x^2 = (2-x)^2</math>

<math>x^2 = 4 - 4x + x^2</math>

<math>0 = 4 - 4x</math>

<math>4x = 4</math>

<math>x = 1</math>

Ainsi la somme est la plus base lorsque <math>x = 1</math>.
On en conclut que <math>f(x) \geq 2\sqrt{1^2 + h^2}, \forall x \in \mathbb{R}</math>, avec égalité pour <math>x = 1</math>

Ainsi nous avons démontré que la somme des distances est la plus basse lorsque <math>x</math> vaut la moitie de la base du triangle comportant les deux triangles rectangles.
Ce qui devient le triangle <strong style="color:#FFCE00">jaune</strong> dans la Figure 2.

[[Fichier:Briffod_Figure_2.png|400px|thumb|center|Figure n° 2]]

Le même argument s'applique pour la somme des distances aux maisons M3 et M4. En une deuxième étape, le même argument est appliqué pour la somme des distances de A aux maisons M2 et M3, respectivement
M1 et M4, justifiant ainsi que la position optimale et au centre du rectangle.

Nous venons ainsi de démontrer où se trouve le point minimisant la distance moyenne à quatre points dans un rectangle.

Dans la suite, nous souhaitons proposer une méthode numérique pour trouver la position optimale, dans des cas généraux.
Cette méthode est basé sur l'analyse du gradient.

== Gradient ==
Affin d'illustrer la méthode du gradient, imaginons que nous souhaitons minimiser une fonction convexe à une variable.

Nous allons alors prendre un point aléatoire sur la courbe (<strong style="color:#0080FF">a0</strong>), puis l'on calcule la pente de la courbe à ce point, on utilise alors la dérivée
(si notre fonction à minimiser prend plusieurs paramètres alors on calcule les dérivées partielles pour chacun des paramètres).
Le calcul de cette dérivée nous donne la direction de la pente, puis on avance d'un petit pas nommé <strong style="color:#008020">alpha</strong> dans la direction de la descente.
Ce qui nous amène à une seconde position (<strong style="color:#0080FF">a1</strong>) et on recalcule la dérivée en répétant la procédure, jusqu'avoir convergé au <strong style="color:#FF0000">minimum</strong> de notre fonction.

[[Fichier:Briffod_Figure_3.png|400px|thumb|center|Figure n° 3]]

== Où situer une antenne 5G dans un village ? ==
Ainsi l'on peut écrire un algorithme qui permet de trouver le point de l'antenne qui minimise la distance moyenne dans un village qui peut avoir une forme géométrique générale. Petite information a noter alpha doit être choisis judicieusement puisqu'on pourrait directement au bout de quelques itérations de la boucle dépasser le minimum, ce qui m'avait poser des problèmes.

Exemple de la méthode du gradient avec différentes figures :

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_carre.png|600px|center|Exemple d'un carré]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_triangle.png|600px|center|Exemple d'un triangle équilatéral]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_pont.png|600px|center|Exemple d'un "Pont"]]
</div>
</div>

== Diagramme de Voronoï ==

Le diagramme de Voronoï est une division en "cellules" d’un plan, basée sur un ensemble de points donnés (les antennes, dans cet exemple).
Chaque cellule contient tous les points du plan qui sont les plus proches d’une antenne par rapport aux autres.

Ce diagramme est utilisé en géométrie, en cartographie, en biologie, et dans de nombreux autres domaines, notamment pour modéliser des zones d’influence.

Imaginons maintenant que nous ayons 2, 3 ou 4 antennes 5G déjà positionnées dans notre village.
Si chaque maison se connecte à l’antenne la plus proche, alors un diagramme de Voronoï apparaîtrait naturellement.

J'ai ainsi mis en œuvre un algorithme permettant de réaliser des diagrammes de Voronoï peu importe la forme de la figure, de manière naïve sans optimisation.
Les antennes 5G sont représentées par les points <strong style="color:black">noirs</strong>. <strong style="color:black">
Les antennes</strong> ont été placées de manière aléatoire dans le village affin de pouvoir observer à quoi ressemble un diagramme de Voronoï.
De plus j'ai modifié la forme du village pour observer différents exemples.

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_carre_Voronoï.png|600px|center|Exemple d'un carré]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_etoile_Voronoï.png|600px|center|Exemple d'une étoile]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_pont_Voronoï.png|600px|center|Exemple d'un "Pont"]]
</div>
</div>

Dans ce cas, toutes les maisons situées dans une cellule de couleur sont plus proches de <strong style="color:black">l'antenne</strong> dans leur cellule que de n'importe quelle autre.

Il est important de noter que les frontières entre les cellules ne sont pas linéaires, elles sont en escalier. Cela est du à la représentation graphique, à la représentation numérique (calcul sur des flottants) et à la densité des points sur le graphique.
Par soucis d'efficacité j'ai choisi le meilleur rapport densité/temps de calcul.

* Si les points (antennes) sont bien placés — c’est-à-dire répartis de manière optimale (pas verticalement) par rapport à la distribution des maisons — alors :
** Les cellules de Voronoï deviennent plus petites et plus équilibrées ;
** Chaque antenne couvre une zone plus compacte ;
** Les maisons sont donc plus proches de leur antenne ;
** Résultat : une meilleure efficacité de couverture.

== Où situer plusieurs antennes 5G dans un village ? ==
C'est une bonne chose de pouvoir observer quelle région se connecte à quelle antenne, mais il faut à présent bien placer les antennes.

Je n'ai pas réussi à mettre en œuvre une méthode de gradient (2 dérivées partielles par antenne).
Par conséquent, je me suis orienté vers un autre algorithme : Le Recuit Simulé.

Pourquoi avoir choisis cet algorithme ?
L'avantage principale de cet algorithme c'est qu'il à été conçu pour éviter d'être bloqué dans un minimum local.
Malheureusement l'algorithme baisse en précision et on ne peux pas être sûr que le résultat soit optimal.

C'est pour ça que je vous invite à comparer les résultats du carré avec des résultats prouvés mathématiquement par Morgan F. & Bolton R: [https://www.tandfonline.com/doi/abs/10.1080/00029890.2002.11919849 lien de l'article]

Comment fonctionne le Recuit Simulé ?
* On génère <math>n</math> antennes de manière aléatoire dans la figure -> antenne initiale.
* On calcule le coût, ici la distance moyenne de chaque maison à l'antenne.
On boucle les étape suivantes pour chaque itération :
* On perturbe la solution, on déplace une antenne au hasard d'un petit pas dans le village.
* On calcule le nouveau coût
* Si le nouveau coût est meilleur, on garde le changement
* Sinon on accepte parfois le changement avec une probabilité de garder la modification qui diminue avec le temps, ce qui permet de ne pas rester bloquer dans un minimum local.
* puis l'on arrête si l'on a pas trouvé mieux depuis longtemps, où après un nombre d'itération maximal.

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_9_bonnes_antennes.png|600px|center|Exemple d'un carré avec 9 antennes]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_8_bonnes_antennes.png|600px|center|Exemple d'un carré avec 8 antennes]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_5_bonnes_antennes.png|600px|center|Exemple d'une étoile avec 5 antennes]]
</div>
</div>

On notera que les points ne sont pas optimaux, cela est du à l'algorithme utilisé, à la représentation graphique, à la représentation numérique (calcul sur des flottants) et à la densité des points sur le graphique.
Par soucis d'efficacité j'ai choisis le meilleur rapport densité/temps de calcul.

Exemple de la répartition de 6 antennes dans un carré au fur et à mesure des itérations :
[[Fichier:Briffod_Gif_voronoi.gif|600px|center|Exemple de la répartition de 6 antennes]]

== Organisation optimale des antennes ==

Si l'on fait tourner cet algorithme avec de plus en plus d'antennes, l'on remarquera que les antennes seront disposées de manière hexagonale, est-ce un hasard ?

Dans un contexte de pavage optimal du plan, l’hexagone régulier est la forme géométrique qui minimise le rapport entre le périmètre total et la surface couverte lorsqu’un grand nombre de cellules identiques doivent remplir un plan sans chevauchement ni intersection. Ce résultat est formalisé par le théorème du nid d’abeille, démontré rigoureusement par Thomas C. Hales en 2001, qui prouve que parmi toutes les divisions possibles du plan en cellules de surface égale, le pavage hexagonal possède le périmètre total minimal. Ce principe explique pourquoi les structures naturelles comme les alvéoles des abeilles adoptent une organisation hexagonale.
De manière analogue, en télécommunications, une disposition hexagonale des zones de couverture des antennes optimise l’efficacité de couverture, réduit les zones mortes et uniformise la répartition des ressources réseau sur une large surface, ce qui est essentiel dans la conception des réseaux cellulaires.

Thomas C. Hales (2001),
The Honeycomb Conjecture,
Discrete & Computational Geometry, vol. 25, pp. 1–22,
DOI: 10.1007/s004540010071.

== Conclusion ==

Pour placer des antennes dans un village, il faut les positionner de manière à minimiser les zones sans couverture (dans le cas où l'on ajouterait une distance maximum pour se connecter à une antenne) tout en répartissant les antennes uniformément,
idéalement selon un motif hexagonal pour maximiser l’efficacité et la compacité.

== Source ==

[https://youtu.be/rcl_YRyoLIY?feature=shared&t=178 Descente de Gradient]<br>
[https://youtu.be/GdTFqRK1l44 Série de vidéos sur le Recuit Simulé]<br>
[http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/VISI201_CMI_:_visite_de_laboratoire#Où_placer_une_(ou_plusieurs)_antennes_5G_dans_un_village_? Références jointes au sujet]<br>

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-05-15T19:32:42Z

Briffod :

Élève : Briffod Nils

Tuteur : Dorin Bucur

== Introduction ==

Au travers de ce sujet, nous allons réfléchir, réaliser un model mathématique puis le mettre en pratique grâce aux outils informatiques.
Nous parlerons de graphes et d'optimisation de longueurs.

== Problématique ==

En quoi consiste ce problème mathématique relié à un exemple concret ?
Nous cherchons à minimiser la distance moyenne entre chaque maisons et l'antenne 5G.
Autrement dis dans une surface donnée, de forme quelconque, nous devons être capable de trouver les coordonnées optimales du point où l'antenne y sera placer.
Bien que cette question à été simplifiée, elle repose sur un concept mathématique important notamment au sujet de la planification économique.

== Démonstration ==
Comment déterminé le point où la distance moyenne entre le point de l'antenne et tous les autres points de la figure ?

Cette démonstration est basée sur un article de recherche par Morgan F. & Bolton R. (2002) publié par une revue scientifique, [https://www.tandfonline.com/doi/abs/10.1080/00029890.2002.11919849 lien de l'article]

Nous sommes dans un rectangle est nous allons démontrer ceci sur la largeur d'un coté du rectangle, comme dans la Figure 1.
Nous cherchons a diminuer au la somme des longueurs des cotés des deux triangles rectangles (le rouge et le bleu) formant un triangle quelconque tout en gardant une hauteur constante non définie. Par ailleurs seulement deux des trois cotés des triangles nous intéresses puisque le troisième est commun a tous les triangle de notre exemple.

[[Fichier:Figure_1.png|400px|thumb|center|Figure n° 1]]

Concentrons nous sur les triangles rectangles.
Nous allons déterminer grâce au théorème de Pythagore les longueurs des côtes des triangles:
*Le triangle rectangle <strong style="color:#FF0000">rouge</strong> a pour longueur de coté : <math>x</math>, <math>h</math> et pour hypoténuse : <math>\sqrt{x^2 + h^2}</math>
*Le triangle rectangle <strong style="color:#0080FF">bleu</strong> a pour longueur de coté : <math>2-x</math>, <math>h</math> et pour hypoténuse : <math>\sqrt{(2-x)^2 + h^2}</math>

i.e. Nous allons faire varier <math>x</math> et observer là où la fonction de la somme est au minimum.
Définissons notre fonction de la somme de la longueur des côtes des triangles:
<math>f(x) = \sqrt{(2-x)^2 + h^2} + \sqrt{x^2 + h^2}</math>
Cherchons quand <math>f(x) \geq 2 \sqrt{1^2 + h^2}</math> :

On minimise <math>f(x)</math> ce qui reviens a chercher quand sa dérivé s'annule.
*<math>f'(x)\geq 0</math> :
<math>-\frac{2-x}{\sqrt{(2-x)^2 + h^2}} + \frac{x}{\sqrt{x^2 + h^2}} = 0</math>

<math>\frac{x}{\sqrt{x^2 + h^2}} = \frac{2-x}{\sqrt{(2-x)^2 + h^2}}</math>

<math>\frac{x^2}{x^2 + h^2} = \frac{(2-x)^2}{(2-x)^2 + h^2}</math>

<math>x^2 (2-x)^2 + x^2 h^2 = (2-x)^2 x^2 + (2-x)^2 h^2</math>

<math>x^2 h^2 = (2-x)^2 h^2</math>

<math>x^2 = (2-x)^2</math>

<math>x^2 = 4 - 4x + x^2</math>

<math>0 = 4 - 4x</math>

<math>4x = 4</math>

<math>x = 1</math>

Ainsi la somme est la plus base lorsque <math>x = 1</math>,
On en conclus que <math>f(x) \geq 2\sqrt{1^2 + h^2}, \forall x \in \mathbb{R}</math>

Ainsi nous avons démontrer que la somme des distances est la plus basse lorsque <math>x</math> vaut la moitie de la base du triangle comportant les deux triangles rectangles.
Ce qui devient le triangle <strong style="color:#FFCE00">jaune</strong> dans la Figure 2.

[[Fichier:Briffod_Figure_2.png|400px|thumb|center|Figure n° 2]]

En faisant la même démonstration cette fois ci en prenant le triangle <strong style="color:#0080FF">bleu</strong> et le triangle <strong style="color:#FF0000">rouge</strong> sur la largeur du triangle rectangle, on trouve que le point qui minimise la distance moyenne d'un rectangle est le centre géométrique du rectangle.
Nous venons ainsi de démontrer où se trouve le point minimisant la distance moyenne à quatre points dans un rectangle.

== Gradient ==

Un des prérequis pour utiliser la méthode gradient, c'est de vouloir minimiser une fonction qui est sur tout son ensemble de définition convexe.
Nous allons alors prendre un point aléatoire sur la courbe (<strong style="color:#0080FF">a0</strong>), puis l'on calcul la pente de la courbe à ce point, on utilise alors la dérivée
et si notre fonction à minimiser prends plusieurs paramètre alors on calcule la dérivée partielle pour chacun des paramètres.
Le calcul de cette dérivé nous donne la direction de la pente qui descends, puis on avance d'un petit pas nommé <strong style="color:#008020">alpha</strong>.
Ce qui nous amène à une seconde position (<strong style="color:#0080FF">a1</strong>) et on recalcule la dérivée jusqu'à ce que la pente réaugmente, on aura converger au <strong style="color:#FF0000">minimum</strong> de notre fonction.

[[Fichier:Briffod_Figure_3.png|400px|thumb|center|Figure n° 3]]

== Où situer une antenne 5G dans un village ? ==
Ainsi l'on peut écrire un algorithme qui permet de trouver le point de l'antenne qui minimise la distance moyenne. Petite information a noter alpha doit être choisis judicieusement puisqu'on pourrait directement au bout de quelques itérations de la boucle dépasser le minimum, ce qui m'avait poser des problèmes. Exemple avec différentes figures :

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_carre.png|600px|center|Exemple d'un carré]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_triangle.png|600px|center|Exemple d'un triangle équilatéral]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_pont.png|600px|center|Exemple d'un "Pont"]]
</div>
</div>

== Diagramme de Voronoï ==

Le diagramme de Voronoï est une division en "cellules" d’un plan, basée sur un ensemble de points donnés (les antennes, dans cet exemple).
Chaque cellule contient tous les points du plan qui sont les plus proches d’une antenne par rapport aux autres.

Ce diagramme est utilisé en géométrie, en cartographie, en biologie, et dans de nombreux autres domaines, notamment pour modéliser des zones d’influence.

Imaginons maintenant que nous ayons 2, 3 ou 4 antennes 5G déjà positionnées dans notre village.
Si chaque maison se connecte à l’antenne la plus proche, alors un diagramme de Voronoï apparaîtrait naturellement.

J'ai ainsi réalisé un algorithme permettant de réaliser des diagrammes de Voronoï peut importe la forme de la figure, de manière naïve sans optimisation.
Les antennes 5G sont représentées par les points <strong style="color:black">noirs</strong>. <strong style="color:black">
Les antennes</strong> ont été placées de manière aléatoire dans le village affin de pouvoir observer à quoi ressemble un diagramme de Voronoï.
De plus j'ai modifié la forme du village pour observer différents exemples.

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_carre_Voronoï.png|600px|center|Exemple d'un carré]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_etoile_Voronoï.png|600px|center|Exemple d'une étoile]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_pont_Voronoï.png|600px|center|Exemple d'un "Pont"]]
</div>
</div>

Dans ce cas, toutes les maisons situées dans une cellule de couleur sont plus proches de <strong style="color:black">l'antenne</strong> dans leur cellule que de n'importe quelle autre.

Il est important de noter que les frontière entre les cellules ne sont pas linéaire, elles sont floues, en escalier. Cela est du à la représentation graphique, à la représentation numérique (calcul sur des flottants) et à la densité des points sur le graphique.
Par soucis d'efficacité j'ai choisis le meilleur rapport densité/temps de calcul.

* Si les points (antennes) sont bien placés — c’est-à-dire répartis de manière optimale (pas verticalement) par rapport à la distribution des maisons — alors :
** Les cellules de Voronoï deviennent plus petites et plus équilibrées ;
** Chaque antenne couvre une zone plus compacte ;
** Les maisons sont donc plus proches de leur antenne ;
** Résultat : une meilleure efficacité de couverture.

== Où situer plusieurs antennes 5G dans un village ? ==
C'est une bonne chose de pouvoir observer quelle région se connecte à quelle antenne, mais il faut à présent bien placer les antennes.

Je n'ai pas réussit à réaliser une fonction grâce au gradient (4 dérivées partielles).
Mais pour avoir un résultat, je me suis orienté vers un autre algorithme : Le Recuit Simulé.

Pourquoi avoir choisis cet algorithme ?
L'avantage principale de cet algorithme c'est qu'il à été conçu pour éviter d'être bloquer dans un minimum local.
Malheureusement l'algorithme baisse en complexité ce qui implique que l'on ne peux pas être sûr que le résultat soit optimal.

C'est pour ça que je vous invite à comparer les résultats du carré avec des résultats prouvé mathématiquement : [https://www.tandfonline.com/doi/abs/10.1080/00029890.2002.11919849 lien de l'article]

Comment fonctionne le Recuit Simulé ?
* On génère <math>n</math> antennes de manière aléatoire dans la figure -> antenne initiale.
* On calcule le coût, ici la distance moyenne de chaque maison à l'antenne.
On boucle les étape suivantes pour chaque itération :
* On perturbe la solution, on déplace une antenne au hasard d'un petit pas dans le village.
* On calcul le nouveau coût
* Si le nouveau coût est meilleur, on garde le changement
* Sinon on accepte parfois le changement avec une probabilité de garder la modification qui diminue avec le temps, ce qui permet de ne pas rester bloquer dans un minimum local.
* puis l'on arrête si l'on a pas trouvé mieux depuis longtemps, où après un nombre d'itération maximale.

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_9_bonnes_antennes.png|600px|center|Exemple d'un carré avec 9 antennes]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_8_bonnes_antennes.png|600px|center|Exemple d'un carré avec 8 antennes]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_5_bonnes_antennes.png|600px|center|Exemple d'une étoile avec 5 antennes]]
</div>
</div>

On noteras que les points ne sont pas optimaux, cela est du à l'algorithme utilisé, à la représentation graphique, à la représentation numérique (calcul sur des flottants) et à la densité des points sur le graphique.
Par soucis d'efficacité j'ai choisis le meilleur rapport densité/temps de calcul.

Exemple de la répartition de 6 antennes dans un carré au fur et à mesure des itérations :
[[Fichier:Briffod_Gif_voronoi.gif|600px|center|Exemple de la répartition de 6 antennes]]

== Organisation optimale des antennes ==

Si l'on fait tourner cet algorithme avec de plus en plus d'antenne, l'on remarqueras que les antennes seront disposés de manière hexagonale, est-ce un hasard ?

Dans un contexte de pavage optimal de l’espace, l’hexagone régulier est la forme géométrique qui minimise le rapport entre le périmètre total et la surface couverte lorsqu’un grand nombre de cellules identiques doivent remplir un plan sans chevauchement ni interstice. Ce résultat est formalisé par le théorème du nid d’abeille, démontré rigoureusement par Thomas C. Hales en 2001, qui prouve que parmi toutes les divisions possibles du plan en cellules de surface égale, le pavage hexagonal possède le périmètre total minimal. Ce principe explique pourquoi les structures naturelles comme les alvéoles des abeilles adoptent une organisation hexagonale : il maximise l’efficacité matérielle et énergétique. De manière analogue, en télécommunications, une disposition hexagonale des zones de couverture des antennes optimise l’efficacité de couverture, réduit les zones mortes et uniformise la répartition des ressources réseau sur une large surface, ce qui est essentiel dans la conception des réseaux cellulaires.

Démontrer par :
Thomas C. Hales (2001),
The Honeycomb Conjecture,
Discrete & Computational Geometry, vol. 25, pp. 1–22,
DOI: 10.1007/s004540010071.

== Conclusion ==

Pour placer des antennes dans un village, il faut les positionner de manière à minimiser les zones sans couverture (dans le cas où l'on ajouterais une distance maximum pour se connecter à une antenne) tout en répartissant les antennes uniformément,
idéalement selon un motif hexagonal pour maximiser l’efficacité et la compacité.

== Source ==

[https://youtu.be/rcl_YRyoLIY?feature=shared&t=178 Descente de Gradient]<br>
[https://youtu.be/GdTFqRK1l44 Série de vidéos sur le Recuit Simulé]<br>
[http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/VISI201_CMI_:_visite_de_laboratoire#Où_placer_une_(ou_plusieurs)_antennes_5G_dans_un_village_? Références jointes au sujet]<br>

Fichier:Briffod Gif voronoi.gif

2025-05-15T19:31:06Z

Briffod :

Fichier:Briffod pont.png

2025-05-15T19:26:51Z

Briffod : Briffod a téléversé une nouvelle version de Fichier:Briffod pont.png

Fichier:Briffod carre.png

2025-05-15T19:26:21Z

Briffod : Briffod a téléversé une nouvelle version de Fichier:Briffod carre.png

Fichier:Briffod triangle.png

2025-05-15T19:25:37Z

Briffod : Briffod a téléversé une nouvelle version de Fichier:Briffod triangle.png

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-05-02T13:54:00Z

Briffod : Modification des titres de deux parties

Élève : Briffod Nils

Tuteur : Dorin Bucur

== Introduction ==

Au travers de ce sujet, nous allons réfléchir, réaliser un model mathématique puis le mettre en pratique grâce aux outils informatiques.
Nous parlerons de graphes et d'optimisation de longueurs.

== Problématique ==

En quoi consiste ce problème mathématique relié à un exemple concret ?
Nous cherchons à minimiser la distance moyenne entre chaque maisons et l'antenne 5G.
Autrement dis dans une surface donnée, de forme quelconque, nous devons être capable de trouver les coordonnées optimales du point où l'antenne y sera placer.
Bien que cette question à été simplifiée, elle repose sur un concept mathématique important notamment au sujet de la planification économique.

== Démonstration ==
Comment déterminé le point où la distance moyenne entre le point de l'antenne et tous les autres points de la figure ?

Cette démonstration est basée sur un article de recherche par Morgan, F., & Bolton, R. (2002) publié par une revue scientifique, [https://www.tandfonline.com/doi/abs/10.1080/00029890.2002.11919849 lien de l'article]

Nous sommes dans un rectangle est nous allons démontrer ceci sur la largeur d'un coté du rectangle, comme dans la Figure 1.
Nous cherchons a diminuer au la somme des longueurs des cotés des deux triangles rectangles (le rouge et le bleu) formant un triangle quelconque tout en gardant une hauteur constante non définie. Par ailleurs seulement deux des trois cotés des triangles nous intéresses puisque le troisième est commun a tous les triangle de notre exemple.

[[Fichier:Figure_1.png|400px|thumb|center|Figure n° 1]]

Concentrons nous sur les triangles rectangles.
Nous allons déterminer grâce au théorème de Pythagore les longueurs des côtes des triangles:
*Le triangle rectangle <strong style="color:#FF0000">rouge</strong> a pour longueur de coté : <math>x</math>, <math>h</math> et pour hypoténuse : <math>\sqrt{x^2 + h^2}</math>
*Le triangle rectangle <strong style="color:#0080FF">bleu</strong> a pour longueur de coté : <math>2-x</math>, <math>h</math> et pour hypoténuse : <math>\sqrt{(2-x)^2 + h^2}</math>

i.e. Nous allons faire varier <math>x</math> et observer là où la fonction de la somme est au minimum.
Définissons notre fonction de la somme de la longueur des côtes des triangles:
<math>f(x) = \sqrt{(2-x)^2 + h^2} + \sqrt{x^2 + h^2}</math>
Cherchons quand <math>f(x) \geq 2 \sqrt{1^2 + h^2}</math> :

On minimise <math>f(x)</math> ce qui reviens a chercher quand sa dérivé s'annule.
*<math>f'(x)\geq 0</math> :
<math>-\frac{2-x}{\sqrt{(2-x)^2 + h^2}} + \frac{x}{\sqrt{x^2 + h^2}} = 0</math>

<math>\frac{x}{\sqrt{x^2 + h^2}} = \frac{2-x}{\sqrt{(2-x)^2 + h^2}}</math>

<math>\frac{x^2}{x^2 + h^2} = \frac{(2-x)^2}{(2-x)^2 + h^2}</math>

<math>x^2 (2-x)^2 + x^2 h^2 = (2-x)^2 x^2 + (2-x)^2 h^2</math>

<math>x^2 h^2 = (2-x)^2 h^2</math>

<math>x^2 = (2-x)^2</math>

<math>x^2 = 4 - 4x + x^2</math>

<math>0 = 4 - 4x</math>

<math>4x = 4</math>

<math>x = 1</math>

Ainsi la somme est la plus base lorsque <math>x = 1</math>,
On en conclus que <math>f(x) \geq 2\sqrt{1^2 + h^2}, \forall x \in \mathbb{R}</math>

Ainsi nous avons démontrer que la somme des distances est la plus basse lorsque <math>x</math> vaut la moitie de la base du triangle comportant les deux triangles rectangles.
Ce qui devient le triangle <strong style="color:#FFCE00">jaune</strong> dans la Figure 2.

[[Fichier:Briffod_Figure_2.png|400px|thumb|center|Figure n° 2]]

En faisant la même démonstration cette fois ci en prenant le triangle <strong style="color:#0080FF">bleu</strong> et le triangle <strong style="color:#FF0000">rouge</strong> sur la largeur du triangle rectangle, on trouve que le point qui minimise la distance moyenne d'un rectangle est le centre géométrique du rectangle.
Nous venons ainsi de démontrer où se trouve le point minimisant la distance moyenne à quatre points dans un rectangle.

== Gradient ==

Un des prérequis pour utiliser la méthode gradient, c'est de vouloir minimiser une fonction qui est sur tout son ensemble de définition convexe.
Nous allons alors prendre un point aléatoire sur la courbe (<strong style="color:#0080FF">a0</strong>), puis l'on calcul la pente de la courbe à ce point, on utilise alors la dérivée
et si notre fonction à minimiser prends plusieurs paramètre alors on calcule la dérivée partielle pour chacun des paramètres.
Le calcul de cette dérivé nous donne la direction de la pente qui descends, puis on avance d'un petit pas nommé <strong style="color:#008020">alpha</strong>.
Ce qui nous amène à une seconde position (<strong style="color:#0080FF">a1</strong>) et on recalcule la dérivée jusqu'à ce que la pente réaugmente, on aura converger au <strong style="color:#FF0000">minimum</strong> de notre fonction.

[[Fichier:Briffod_Figure_3.png|400px|thumb|center|Figure n° 3]]

== Où situer une antenne 5G dans un village ? ==
Ainsi l'on peut écrire un algorithme qui permet de trouver le point de l'antenne qui minimise la distance moyenne. Petite information a noter alpha doit être choisis judicieusement puisqu'on pourrait directement au bout de quelques itérations de la boucle dépasser le minimum, ce qui m'avait poser des problèmes. Exemple avec différentes figures :

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_carre.png|600px|center|Exemple d'un carré]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_triangle.png|600px|center|Exemple d'un triangle équilatéral]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_pont.png|600px|center|Exemple d'un "Pont"]]
</div>
</div>

== Diagramme de Voronoï ==

Le diagramme de Voronoï est une division en "cellules" d’un plan, basée sur un ensemble de points donnés (les antennes, dans cet exemple).
Chaque cellule contient tous les points du plan qui sont les plus proches d’une antenne par rapport aux autres.

Ce diagramme est utilisé en géométrie, en cartographie, en biologie, et dans de nombreux autres domaines, notamment pour modéliser des zones d’influence.

Imaginons maintenant que nous ayons 2, 3 ou 4 antennes 5G déjà positionnées dans notre village.
Si chaque maison se connecte à l’antenne la plus proche, alors un diagramme de Voronoï apparaîtrait naturellement.

J'ai ainsi réalisé un algorithme permettant de réaliser des diagrammes de Voronoï peut importe la forme de la figure, de manière naïve sans optimisation.
Les antennes 5G sont représentées par les points <strong style="color:black">noirs</strong>. <strong style="color:black">
Les antennes</strong> ont été placées de manière aléatoire dans le village affin de pouvoir observer à quoi ressemble un diagramme de Voronoï.
De plus j'ai modifié la forme du village pour observer différents exemples.

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_carre_Voronoï.png|600px|center|Exemple d'un carré]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_etoile_Voronoï.png|600px|center|Exemple d'une étoile]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_pont_Voronoï.png|600px|center|Exemple d'un "Pont"]]
</div>
</div>

Dans ce cas, toutes les maisons situées dans une cellule de couleur sont plus proches de <strong style="color:black">l'antenne</strong> dans leur cellule que de n'importe quelle autre.

Il est important de noter que les frontière entre les cellules ne sont pas linéaire, elles sont floues, en escalier. Cela est du à la représentation graphique, à la représentation numérique (calcul sur des flottants) et à la densité des points sur le graphique.
Par soucis d'efficacité j'ai choisis le meilleur rapport densité/temps de calcul.

* Si les points (antennes) sont bien placés — c’est-à-dire répartis de manière optimale (pas verticalement) par rapport à la distribution des maisons — alors :
** Les cellules de Voronoï deviennent plus petites et plus équilibrées ;
** Chaque antenne couvre une zone plus compacte ;
** Les maisons sont donc plus proches de leur antenne ;
** Résultat : une meilleure efficacité de couverture.

== Où situer plusieurs antennes 5G dans un village ? ==
C'est une bonne chose de pouvoir observer quelle région se connecte à quelle antenne, mais il faut à présent bien placer les antennes.

Je n'ai pas réussit à réaliser une fonction grâce au gradient (4 dérivées partielles).
Mais pour avoir un résultat, je me suis orienté vers un autre algorithme : Le Recuit Simulé.

Pourquoi avoir choisis cet algorithme ?
L'avantage principale de cet algorithme c'est qu'il à été conçu pour éviter d'être bloquer dans un minimum local.
Malheureusement l'algorithme baisse en complexité ce qui implique que l'on ne peux pas être sûr que le résultat soit optimal.

C'est pour ça que je vous invite à comparer les résultats du carré avec des résultats prouvé mathématiquement : [https://www.tandfonline.com/doi/abs/10.1080/00029890.2002.11919849 lien de l'article]

Comment fonctionne le Recuit Simulé ?
* On génère <math>n</math> antennes de manière aléatoire dans la figure -> antenne initiale.
* On calcule le coût, ici la distance moyenne de chaque maison à l'antenne.
On boucle les étape suivantes pour chaque itération :
* On perturbe la solution, on déplace une antenne au hasard d'un petit pas dans le village.
* On calcul le nouveau coût
* Si le nouveau coût est meilleur, on garde le changement
* Sinon on accepte parfois le changement avec une probabilité de garder la modification qui diminue avec le temps, ce qui permet de ne pas rester bloquer dans un minimum local.
* puis l'on arrête si l'on a pas trouvé mieux depuis longtemps, où après un nombre d'itération maximale.

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_9_bonnes_antennes.png|600px|center|Exemple d'un carré avec 9 antennes]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_8_bonnes_antennes.png|600px|center|Exemple d'un carré avec 8 antennes]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_5_bonnes_antennes.png|600px|center|Exemple d'une étoile avec 5 antennes]]
</div>
</div>

On noteras que les points ne sont pas optimaux, cela est du à l'algorithme utilisé, à la représentation graphique, à la représentation numérique (calcul sur des flottants) et à la densité des points sur le graphique.
Par soucis d'efficacité j'ai choisis le meilleur rapport densité/temps de calcul.

== Organisation optimale des antennes ==

Si l'on fait tourner cet algorithme avec de plus en plus d'antenne, l'on remarqueras que les antennes seront disposés de manière hexagonale, est-ce un hasard ?

Dans un contexte de pavage optimal de l’espace, l’hexagone régulier est la forme géométrique qui minimise le rapport entre le périmètre total et la surface couverte lorsqu’un grand nombre de cellules identiques doivent remplir un plan sans chevauchement ni interstice. Ce résultat est formalisé par le théorème du nid d’abeille, démontré rigoureusement par Thomas C. Hales en 2001, qui prouve que parmi toutes les divisions possibles du plan en cellules de surface égale, le pavage hexagonal possède le périmètre total minimal. Ce principe explique pourquoi les structures naturelles comme les alvéoles des abeilles adoptent une organisation hexagonale : il maximise l’efficacité matérielle et énergétique. De manière analogue, en télécommunications, une disposition hexagonale des zones de couverture des antennes optimise l’efficacité de couverture, réduit les zones mortes et uniformise la répartition des ressources réseau sur une large surface, ce qui est essentiel dans la conception des réseaux cellulaires.

Démontrer par :
Thomas C. Hales (2001),
The Honeycomb Conjecture,
Discrete & Computational Geometry, vol. 25, pp. 1–22,
DOI: 10.1007/s004540010071.

== Conclusion ==

Pour placer des antennes dans un village, il faut les positionner de manière à minimiser les zones sans couverture tout en répartissant les antennes uniformément,
idéalement selon un motif hexagonal pour maximiser l’efficacité et la compacité.

== Source ==

[https://youtu.be/rcl_YRyoLIY?feature=shared&t=178 Descente de Gradient]<br>
[https://youtu.be/GdTFqRK1l44 Série de vidéos sur le Recuit Simulé]<br>
[http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/VISI201_CMI_:_visite_de_laboratoire#Où_placer_une_(ou_plusieurs)_antennes_5G_dans_un_village_? Références jointes au sujet]<br>

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-05-01T20:51:09Z

Briffod : Ecriture des parties de 7 à 10

Élève : Briffod Nils

Tuteur : Dorin Bucur

== Introduction ==

Au travers de ce sujet, nous allons réfléchir, réaliser un model mathématique puis le mettre en pratique grâce aux outils informatiques.
Nous parlerons de graphes et d'optimisation de longueurs.

== Problématique ==

En quoi consiste ce problème mathématique relié à un exemple concret ?
Nous cherchons à minimiser la distance moyenne entre chaque maisons et l'antenne 5G.
Autrement dis dans une surface donnée, de forme quelconque, nous devons être capable de trouver les coordonnées optimales du point où l'antenne y sera placer.
Bien que cette question à été simplifiée, elle repose sur un concept mathématique important notamment au sujet de la planification économique.

== Démonstration ==
Comment déterminé le point où la distance moyenne entre le point de l'antenne et tous les autres points de la figure ?

Cette démonstration est basée sur un article de recherche par Morgan, F., & Bolton, R. (2002) publié par une revue scientifique, [https://www.tandfonline.com/doi/abs/10.1080/00029890.2002.11919849 lien de l'article]

Nous sommes dans un rectangle est nous allons démontrer ceci sur la largeur d'un coté du rectangle, comme dans la Figure 1.
Nous cherchons a diminuer au la somme des longueurs des cotés des deux triangles rectangles (le rouge et le bleu) formant un triangle quelconque tout en gardant une hauteur constante non définie. Par ailleurs seulement deux des trois cotés des triangles nous intéresses puisque le troisième est commun a tous les triangle de notre exemple.

[[Fichier:Figure_1.png|400px|thumb|center|Figure n° 1]]

Concentrons nous sur les triangles rectangles.
Nous allons déterminer grâce au théorème de Pythagore les longueurs des côtes des triangles:
*Le triangle rectangle <strong style="color:#FF0000">rouge</strong> a pour longueur de coté : <math>x</math>, <math>h</math> et pour hypoténuse : <math>\sqrt{x^2 + h^2}</math>
*Le triangle rectangle <strong style="color:#0080FF">bleu</strong> a pour longueur de coté : <math>2-x</math>, <math>h</math> et pour hypoténuse : <math>\sqrt{(2-x)^2 + h^2}</math>

i.e. Nous allons faire varier <math>x</math> et observer là où la fonction de la somme est au minimum.
Définissons notre fonction de la somme de la longueur des côtes des triangles:
<math>f(x) = \sqrt{(2-x)^2 + h^2} + \sqrt{x^2 + h^2}</math>
Cherchons quand <math>f(x) \geq 2 \sqrt{1^2 + h^2}</math> :

On minimise <math>f(x)</math> ce qui reviens a chercher quand sa dérivé s'annule.
*<math>f'(x)\geq 0</math> :
<math>-\frac{2-x}{\sqrt{(2-x)^2 + h^2}} + \frac{x}{\sqrt{x^2 + h^2}} = 0</math>

<math>\frac{x}{\sqrt{x^2 + h^2}} = \frac{2-x}{\sqrt{(2-x)^2 + h^2}}</math>

<math>\frac{x^2}{x^2 + h^2} = \frac{(2-x)^2}{(2-x)^2 + h^2}</math>

<math>x^2 (2-x)^2 + x^2 h^2 = (2-x)^2 x^2 + (2-x)^2 h^2</math>

<math>x^2 h^2 = (2-x)^2 h^2</math>

<math>x^2 = (2-x)^2</math>

<math>x^2 = 4 - 4x + x^2</math>

<math>0 = 4 - 4x</math>

<math>4x = 4</math>

<math>x = 1</math>

Ainsi la somme est la plus base lorsque <math>x = 1</math>,
On en conclus que <math>f(x) \geq 2\sqrt{1^2 + h^2}, \forall x \in \mathbb{R}</math>

Ainsi nous avons démontrer que la somme des distances est la plus basse lorsque <math>x</math> vaut la moitie de la base du triangle comportant les deux triangles rectangles.
Ce qui devient le triangle <strong style="color:#FFCE00">jaune</strong> dans la Figure 2.

[[Fichier:Briffod_Figure_2.png|400px|thumb|center|Figure n° 2]]

En faisant la même démonstration cette fois ci en prenant le triangle <strong style="color:#0080FF">bleu</strong> et le triangle <strong style="color:#FF0000">rouge</strong> sur la largeur du triangle rectangle, on trouve que le point qui minimise la distance moyenne d'un rectangle est le centre géométrique du rectangle.
Nous venons ainsi de démontrer où se trouve le point minimisant la distance moyenne à quatre points dans un rectangle.

== Gradient ==

Un des prérequis pour utiliser la méthode gradient, c'est de vouloir minimiser une fonction qui est sur tout son ensemble de définition convexe.
Nous allons alors prendre un point aléatoire sur la courbe (<strong style="color:#0080FF">a0</strong>), puis l'on calcul la pente de la courbe à ce point, on utilise alors la dérivée
et si notre fonction à minimiser prends plusieurs paramètre alors on calcule la dérivée partielle pour chacun des paramètres.
Le calcul de cette dérivé nous donne la direction de la pente qui descends, puis on avance d'un petit pas nommé <strong style="color:#008020">alpha</strong>.
Ce qui nous amène à une seconde position (<strong style="color:#0080FF">a1</strong>) et on recalcule la dérivée jusqu'à ce que la pente réaugmente, on aura converger au <strong style="color:#FF0000">minimum</strong> de notre fonction.

[[Fichier:Briffod_Figure_3.png|400px|thumb|center|Figure n° 3]]

== Où situer une église dans un village ? ==
Ainsi l'on peut écrire un algorithme qui permet de trouver le point de l'antenne qui minimise la distance moyenne. Petite information a noter alpha doit être choisis judicieusement puisqu'on pourrait directement au bout de quelques itérations de la boucle dépasser le minimum, ce qui m'avait poser des problèmes. Exemple avec différentes figures :

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_carre.png|600px|center|Exemple d'un carré]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_triangle.png|600px|center|Exemple d'un triangle équilatéral]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_pont.png|600px|center|Exemple d'un "Pont"]]
</div>
</div>

== Diagramme de Voronoï ==

Le diagramme de Voronoï est une division en "cellules" d’un plan, basée sur un ensemble de points donnés (les antennes, dans cet exemple).
Chaque cellule contient tous les points du plan qui sont les plus proches d’une antenne par rapport aux autres.

Ce diagramme est utilisé en géométrie, en cartographie, en biologie, et dans de nombreux autres domaines, notamment pour modéliser des zones d’influence.

Imaginons maintenant que nous ayons 2, 3 ou 4 antennes 5G déjà positionnées dans notre village.
Si chaque maison se connecte à l’antenne la plus proche, alors un diagramme de Voronoï apparaîtrait naturellement.

J'ai ainsi réalisé un algorithme permettant de réaliser des diagrammes de Voronoï peut importe la forme de la figure, de manière naïve sans optimisation.
Les antennes 5G sont représentées par les points <strong style="color:black">noirs</strong>. <strong style="color:black">
Les antennes</strong> ont été placées de manière aléatoire dans le village affin de pouvoir observer à quoi ressemble un diagramme de Voronoï.
De plus j'ai modifié la forme du village pour observer différents exemples.

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_carre_Voronoï.png|600px|center|Exemple d'un carré]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_etoile_Voronoï.png|600px|center|Exemple d'une étoile]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_pont_Voronoï.png|600px|center|Exemple d'un "Pont"]]
</div>
</div>

Dans ce cas, toutes les maisons situées dans une cellule de couleur sont plus proches de <strong style="color:black">l'antenne</strong> dans leur cellule que de n'importe quelle autre.

Il est important de noter que les frontière entre les cellules ne sont pas linéaire, elles sont floues, en escalier. Cela est du à la représentation graphique, à la représentation numérique (calcul sur des flottants) et à la densité des points sur le graphique.
Par soucis d'efficacité j'ai choisis le meilleur rapport densité/temps de calcul.

* Si les points (antennes) sont bien placés — c’est-à-dire répartis de manière optimale (pas verticalement) par rapport à la distribution des maisons — alors :
** Les cellules de Voronoï deviennent plus petites et plus équilibrées ;
** Chaque antenne couvre une zone plus compacte ;
** Les maisons sont donc plus proches de leur antenne ;
** Résultat : une meilleure efficacité de couverture.

== Où situer plusieurs églises dans un village ? ==
C'est une bonne chose de pouvoir observer quelle région se connecte à quelle antenne, mais il faut à présent bien placer les antennes.

Je n'ai pas réussit à réaliser une fonction grâce au gradient (4 dérivées partielles).
Mais pour avoir un résultat, je me suis orienté vers un autre algorithme : Le Recuit Simulé.

Pourquoi avoir choisis cet algorithme ?
L'avantage principale de cet algorithme c'est qu'il à été conçu pour éviter d'être bloquer dans un minimum local.
Malheureusement l'algorithme baisse en complexité ce qui implique que l'on ne peux pas être sûr que le résultat soit optimal.

C'est pour ça que je vous invite à comparer les résultats du carré avec des résultats prouvé mathématiquement : [https://www.tandfonline.com/doi/abs/10.1080/00029890.2002.11919849 lien de l'article]

Comment fonctionne le Recuit Simulé ?
* On génère <math>n</math> antennes de manière aléatoire dans la figure -> antenne initiale.
* On calcule le coût, ici la distance moyenne de chaque maison à l'antenne.
On boucle les étape suivantes pour chaque itération :
* On perturbe la solution, on déplace une antenne au hasard d'un petit pas dans le village.
* On calcul le nouveau coût
* Si le nouveau coût est meilleur, on garde le changement
* Sinon on accepte parfois le changement avec une probabilité de garder la modification qui diminue avec le temps, ce qui permet de ne pas rester bloquer dans un minimum local.
* puis l'on arrête si l'on a pas trouvé mieux depuis longtemps, où après un nombre d'itération maximale.

<div style="text-align:center;">
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_9_bonnes_antennes.png|600px|center|Exemple d'un carré avec 9 antennes]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_8_bonnes_antennes.png|600px|center|Exemple d'un carré avec 8 antennes]]
</div>
<div style="display:inline-block; margin: 10px;">
[[Fichier:Briffod_5_bonnes_antennes.png|600px|center|Exemple d'une étoile avec 5 antennes]]
</div>
</div>

On noteras que les points ne sont pas optimaux, cela est du à l'algorithme utilisé, à la représentation graphique, à la représentation numérique (calcul sur des flottants) et à la densité des points sur le graphique.
Par soucis d'efficacité j'ai choisis le meilleur rapport densité/temps de calcul.

== Organisation optimale des antennes ==

Si l'on fait tourner cet algorithme avec de plus en plus d'antenne, l'on remarqueras que les antennes seront disposés de manière hexagonale, est-ce un hasard ?

Dans un contexte de pavage optimal de l’espace, l’hexagone régulier est la forme géométrique qui minimise le rapport entre le périmètre total et la surface couverte lorsqu’un grand nombre de cellules identiques doivent remplir un plan sans chevauchement ni interstice. Ce résultat est formalisé par le théorème du nid d’abeille, démontré rigoureusement par Thomas C. Hales en 2001, qui prouve que parmi toutes les divisions possibles du plan en cellules de surface égale, le pavage hexagonal possède le périmètre total minimal. Ce principe explique pourquoi les structures naturelles comme les alvéoles des abeilles adoptent une organisation hexagonale : il maximise l’efficacité matérielle et énergétique. De manière analogue, en télécommunications, une disposition hexagonale des zones de couverture des antennes optimise l’efficacité de couverture, réduit les zones mortes et uniformise la répartition des ressources réseau sur une large surface, ce qui est essentiel dans la conception des réseaux cellulaires.

Démontrer par :
Thomas C. Hales (2001),
The Honeycomb Conjecture,
Discrete & Computational Geometry, vol. 25, pp. 1–22,
DOI: 10.1007/s004540010071.

== Conclusion ==

Pour placer des antennes dans un village, il faut les positionner de manière à minimiser les zones sans couverture tout en répartissant les antennes uniformément,
idéalement selon un motif hexagonal pour maximiser l’efficacité et la compacité.

== Source ==

[https://youtu.be/rcl_YRyoLIY?feature=shared&t=178 Descente de Gradient]<br>
[https://youtu.be/GdTFqRK1l44 Série de vidéos sur le Recuit Simulé]<br>
[http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/VISI201_CMI_:_visite_de_laboratoire#Où_placer_une_(ou_plusieurs)_antennes_5G_dans_un_village_? Références jointes au sujet]<br>

Fichier:Briffod 5 bonnes antennes.png

2025-05-01T20:26:29Z

Briffod :

Fichier:Briffod 8 bonnes antennes.png

2025-05-01T20:25:17Z

Briffod :

Fichier:Briffod 9 bonnes antennes.png

2025-05-01T20:24:19Z

Briffod :

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-04-30T14:06:29Z

Briffod : Correction d'une faute d'orthographe dans la partie du diagramme de Voronoï

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-04-30T14:05:21Z

Briffod : Modification de la partie Diagramme de Voronoï

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-04-30T13:53:03Z

Briffod : Modification de la partie Diagramme de Voronoï

Fichier:Briffod etoile Voronoï.png

2025-04-30T13:34:27Z

Briffod :

Fichier:Briffod pont Voronoï.png

2025-04-30T13:33:34Z

Briffod :

Fichier:Briffod carre Voronoï.png

2025-04-30T13:32:29Z

Briffod :

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-04-17T12:43:55Z

Briffod : Ajout de la partie sur le diagramme de Voronoï

Fichier:Briffod voronoï.png

2025-04-17T12:21:01Z

Briffod :

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-04-10T12:29:36Z

Briffod : Modification d'une phrase partie Gradient

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-04-10T11:40:37Z

Briffod : Replacement des images en ligne

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-04-10T11:35:45Z

Briffod :

Fichier:Briffod pont.png

2025-04-10T11:34:00Z

Briffod :

Fichier:Briffod triangle.png

2025-04-10T11:33:24Z

Briffod :

Fichier:Briffod carre.png

2025-04-10T11:32:56Z

Briffod :

Fichier:Briffod Figure 3.png

2025-04-10T10:44:32Z

Briffod : Schéma fonctionnement du Gradient

== Description ==
Schéma fonctionnement du Gradient

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-03-27T09:37:09Z

Briffod : Ajout d'autre couleurs

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-03-27T09:32:18Z

Briffod : Ajout de couleurs dans le texte

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-03-27T09:27:42Z

Briffod :

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-03-27T09:26:02Z

Briffod :

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-03-27T09:24:16Z

Briffod : Modification de la partie Démonstration, ajout d'images ainsi que du texte

Fichier:Figure 1.png

2025-03-27T09:10:53Z

Briffod : Briffod a téléversé une nouvelle version de Fichier:Figure 1.png

Fichier:Briffod Figure 2.png

2025-03-27T09:10:03Z

Briffod :

Fichier:Figure 1.png

2025-03-27T08:58:42Z

Briffod :

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-03-27T08:40:42Z

Briffod : /* Démonstration */

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-03-27T08:38:52Z

Briffod : Utilisation de la balise math pour toutes les expressions mathématiques

Où placer une (ou plusieurs) antennes 5G dans un village ?

2025-02-19T15:07:43Z

Briffod : Page créée avec « Élève : Briffod Nils Tuteur : Dorin Bucur # Introduction : Au travers de ce sujet, nous allons réfléchir, réaliser un model mathématique puis le mettre en pratique grâce aux outils informatiques. Nous parlerons de graphes et d'optimisation de longueurs. #1 Problématique : En quoi consiste ce problème mathématique relié à un exemple concret ? Nous cherchons à minimiser la somme des distances entre chaque maisons et l'antenne 5G. Autrement dis d... »

Élève : Briffod Nils

Tuteur : Dorin Bucur

# Introduction :

Au travers de ce sujet, nous allons réfléchir, réaliser un model mathématique puis le mettre en pratique grâce aux outils informatiques.
Nous parlerons de graphes et d'optimisation de longueurs.

#1 Problématique :

En quoi consiste ce problème mathématique relié à un exemple concret ?
Nous cherchons à minimiser la somme des distances entre chaque maisons et l'antenne 5G.
Autrement dis dans une surface donnée, de forme quelconque, nous devons être capable de trouver les coordonnées optimales du point où l'antenne y sera placer.
Bien que cette question à été simplifiée, elle repose sur un concept mathématique important notamment au sujet de la planification économique.

#2 Démonstration :
Comment déterminé le point où la somme des distances entre ce point et tous les autres points de la figure est minimal ?

Cette démonstration est basée sur un article de recherche par Morgan, F., & Bolton, R. (2002) (mettre le lien)

Nous sommes dans un carré est nous allons démontrer ceci sur la largeur d'un coté du rectangle, comme dans la Figure 1.
Nous cherchons a diminuer au la somme des cotés des deux triangles rectangles formant un triangle quelconque tout en gardant une hauteur constante non définie. Par ailleurs seulement deux des trois cotés nous intéresses puisque le troisième est commun a tous les triangle de notre exemple.

Concentrons nous sur les triangles rectangles.
Nous allons déterminer grâce au théorème de Pythagore les longueurs des côtes des triangles:
*Le triangle rectangle rouge a pour longueur de coté : x, h et pour hypoténuse : √(x²+h²)
*Le triangle rectangle bleu a pour longueur de coté : 2-x, h et pour hypoténuse : √((2-x)²+h²)

i.e. Nous allons faire varier x et observer là où la fonction de la somme est au minimum.
Définissons notre fonction de la somme de la longueur des côtes des triangles:
f(x) = √((2-x)²+h²) + √(x²+h²)
Cherchons quand f(x) >= 2√(1²+h²):

On minimise f(x) ce qui reviens a chercher quand sa dérivé s'annule.
*f'(x) >= 0 :
-(2-x)/√((2-x)²+h²) + x/√(x²+h²) = 0 #h est une constante

<=> x/√(x²+h²) = (2-x)/√((2-x)²+h²) #On permute de l'autre coté un membre de l'équation

<=> x²/(x²+h²) = (2-x)²/((2-x)²+h²) #On élève au carré affin de supprimer les racines

<=> x²*(2-x)² + x²*h² = (2-x)²*x² + (2-x)²*h² #On utilise la règle du produit en croix

<=> x²*h² = (2-x)²*h² #On simplifie par x²*(2-x)² l'équation

<=> x² = (2-x)² #On simplifie par h² l'équation

<=> x² = 4-4x+x² #On développe le membre de gauche

<=> 0 = 4-4x #On soustrait x² à l'équation

<=> 4x = 4 #On ajoute 4x à l'équation

<=> x = 1

Ainsi la somme est la plus base lorsque x = 1,
On en conclus que f(x) >= 2√(1²+h²), ∀ x ∈ ℝ

Ainsi nous avons démontrer que la somme des distances est la plus basse lorsque x vaut la moitie de la base du triangle comportant les deux triangles rectangles.

TODO :
Faire une meilleure mise en page,
insérer les images/liens,
correction des erreurs grammaticales,
finir la rédaction.