Problème du cercle minimum

vignette|Cercles minimaux encerclant des ensembles de points.

En algorithmique et en géométrie, le problème du cercle englobant minimum (ou cercle minimum tout court) consiste à trouver le cercle le plus petit englobant un ensemble borné de points du plan euclidien.

Historique

Le problème de recherche du cercle minimum a été soulevé par James Joseph Sylvester en 1857 :

soit en français En 1885, le professeur M. Chrystal a déterminé le premier algorithme de détermination de ce cercle .

Applications La résolution de ce problème peut servir : à déterminer l'emplacement optimal d'une installation, d'une ressource servant à plusieurs clients (), par exemple un service d'accueil des urgences ou bien un bureau de poste dans une ville ; on parle d'ailleurs parfois du « problème du bureau de poste » ()Ce terme est également utilisé pour décrire le problème de la recherche des plus proches voisins ; il s'agit alors de trouver le bureau de poste le plus proche d'un domicile ; le centre du cercle minimum est l'emplacement qui permet d'avoir le trajet de longueur maximale le plus court — c'est la formulation (P2) ci-dessusDe ce point de vue, on pourra rapprocher le problème du cercle minimal de celui de Fermat-Torricelli-Steiner, dans lequel on cherche un « centre » qui minimise la somme des distances aux points : Pour en apprendre davantage, on pourra consulter la section 11.7 chez et l'article de . — ; cela suppose que l'effort d'accès est proportionnel à la distance à vol d'oiseau ; par ailleurs, il faut se poser la question de la pertinence si la densité de population n'est pas uniforme ; en effet, on peut alors avoir une zone très peuplée loin du centre, parce qu'une zone peu peuplée lui est diamétralement opposée ; il s'agit alors d'un choix politique : veut-on minimiser le trajet pour tous les habitants (favoriser la continuité territoriale) ou bien investir pour avoir statistiquement le meilleur résultat (minimisation du risque) ; déterminer l'emplacement d'un relais de radiotéléphonie nécessitant la puissance d'émission la plus faible pour couvrir des stations d'émission-réception données ; à déterminer le point d'impact et le rayon d'action d'une bombe pour toucher des objectifs déterminés (centre et rayon du cercle minimum) ; de critère de position : si l'on a points expérimentaux (états dont les valeurs des paramètres sont des points dans un espace à dimensions) présentant une dispersion (erreur de mesure, agitation thermique…), alors on considère fréquemment que les valeurs des paramètres sont des variables aléatoires, dont on retient l'espérance mathématique estimée ; on peut à la place retenir le centre de l'hypersphère minimale les contenant tous ; ramené à une dimension, cela revient à prendre le milieu des valeurs extrêmes, ce qui n'est pas le critère le plus pertinent mais est néanmoins un critère simple ; dans le cas des critères de fatigue triaxiale de Matake et de Dang Van, on étudie le trajet que parcourt l'extrémité du vecteur de cisaillement au cours du temps ; on définit la contrainte de cisaillement moyenne comme étant le centre du cercle circonscrit au trajet, c'est-à-dire le cercle minimum contenant tous les points décrits au cours du temps.

Existence et unicité du cercle minimum Étant donné une partie bornée non vide du plan euclidien , on désigne par disque englobant un disque fermé contenant cette partie, et par cercle englobant, la frontière d'un disque englobant.

Existence d'un disque englobant de rayon minimum : l'application qui, à tout point , associe la borne supérieure des distances de aux points de , est continue (car 1-lipschitzienne) et tend vers quand s'éloigne à l'infini, donc elle atteint son minimum , en un point :

Le disque de centre et de rayon est alors un disque englobant de rayon minimum, et le cercle de centre et de rayon un cercle englobant de rayon minimum.

L'unicité de se déduit du théorème de la médiane.

Majoration du rayon du cercle minimum D'après le théorème de Jung, le rayon du cercle minimum vérifie : où est le diamètre de .

Cas triviaux

300px|Cas triviaux cercle minimum

L'ensemble est réduit à un point {A} : il s'agit du cercle dégénéré réduit au point A (cercle de centre A et de rayon 0) ; l'ensemble est une paire de points distincts {A1, A2} : il s'agit du cercle de diamètre [A1A2] ; l'ensemble est un nombre quelconque de points alignés dont au moins deux sont distincts : il s'agit du cercle dont un diamètre relie les deux points les plus éloignés ; l'ensemble est un triplet de points non alignés {A1, A2, A3} : soit c'est un des cercles de diamètre [A1A2], [A2A3] ou [A3A1], soit c'est le cercle passant par les trois points ; plus précisément : si le triangle est obtusangle, le cercle a pour diamètre le côté opposé à l'angle obtus, si le triangle est acutangle ou rectangle, le cercle est circonscrit au triangle. On remarque qu'en dehors du cas dégénéré, le plus grand arc de cercle entre deux points situés sur le cercle est au plus un demi-périmètre ; le cercle passe par au moins deux points de l'ensemble. Ceci reste valable pour points ( > 3).

Propriétés générales dans le cas d'un ensemble fini

Sauf cas exceptionnel, le cercle passe par deux ou par trois points de l'ensemble ; il est très peu probable — voire impossible dans un cas réel — que quatre points ou plus soient sur le cerclePar « cas réel », on entend points dont les coordonnées sont mesurées, donc sont des nombres décimaux avec un nombre de décimales d fixé. Du fait de la densité de dans , le cercle passe par une infinité de points ayant des coordonnées décimales ; toutefois, il n'y en a qu'un nombre limité ayant d décimales. Il est donc très improbable que l'on ait, sur le cercle, un point dont les coordonnées aient au plus d décimales, en dehors des points servant à construire le cercle ; et il est encore plus improbable qu'un tel point fasse partie des points de l'ensemble étudié.. On en déduit donc que : soit le cercle passe par deux points de l'ensemble ; dans ce cas-là, le segment de droite formé par ces deux points est un diamètre du cercle ; soit le cercle passe par trois points de l'ensemble ; dans ce cas-là, le triangle formé par ces trois points n'est pas obtus (triangle acutangle, ou exceptionnellement rectangle).

Algorithmes dans le cas fini

Plusieurs algorithmes ont été développés. Considérons un ensemble de points, appelés « points expérimentaux », et notés A1(1, 1), …, A(xn, yn).

Recherche par essai-erreur

L'algorithme le plus simple consiste à considérer les cercles dont les diamètres sont les segments formés par les points pris deux par deux — il y en a ( – 1)/2 (voir Combinaison (mathématiques)) ; les cercles circonscrits aux triangles formés par les points pris trois par trois — il y en a ( – 1)( – 2)/6 ; et à trouver le plus petit de ces cercles contenant tous les points — il faut donc, pour chaque disque, vérifier si les – 2 ou – 3 points restants sont dans le disque.

L'algorithme a donc une complexité en O(4).

C'est un algorithme simple à mettre en œuvre de manière automatisée, mais il est peu performant.

Algorithme géométrique

400px|vignette|Construction du cercle minimum.

L'approche géométrique consiste à utiliser les propriétés générales présentées ci-dessus. Les méthodes sont simples à mettre en œuvre manuellement — construction à la règle et au compas —, et relativement simples à automatiser (coder). Une première approche prend en compte tous les pointsSmallest Enclosing Circle Problem, Rashid Bin Muhammad, Université de l'État du Kent (États-Unis).

Il faut commencer par prendre un cercle arbitraire contenant toutes les données. Un cercle bien choisi permet de réduire le nombre d'itérations.

Une manière simple de choisir un centre C0 adapté consiste à prendre le centre du rectangle minimum contenant tous les points et aligné sur les axes. Puis, on prend le point expérimental A le plus éloigné de C0. Le cercle de centre C0 et de rayon C0A, donc passant par A, contient tous les points.

Commençons par tracer un cercle initial Γ0 comme déterminé précédemment (centre C0, rayon C0A). Déplacer le centre vers A, jusqu'à ce qu'au moins un autre point, appelé B, soit sur le cercle. Ce cercle Γ1 est inclus (ou égal) dans le cercle précédent.Pour trouver le centre C1, on repère le point B susceptible de convenir, et on utilise le fait que [AB] est une corde. C1 est donc l'intersection de la médiatrice de [AB] et de [C0A]. Le cercle Γ1 passe donc par au moins deux points expérimentaux (A et B). C'est le cercle minimum si [AB] est un diamètre, ou bien s'il passe par un troisième point C, le triangle ABC étant acutangle ; mais il est peu probable que l'on ait déjà la solution.Il y a donc déjà deux points (A et B) sur le cercle. Soient D et E les deux points délimitant le plus grand arc de cercle (cet arc fait plus d'un demi-périmètre) ; il s'agit probablement des points A et B. On peut donc diminuer le rayon du cercle, tout en le laissant passer par ces deux points D et E. On essaie deux cercles : le cercle ayant pour diamètre [DE] ; on repère le point F le plus proche du cercle (celui qui sera touché en premier lorsque le rayon diminue), et on prend le cercle circonscrit au triangle DEF. Il est très probable que l'un des deux cercles soit le cercle minimum. Sinon, c'est que le triangle DEF a un angle obtus ; on considère les points du côté opposé à l'angle obtus, ou, si plus de trois points sont sur le cercle, les points délimitant l'arc le plus grand, et on réitère la dernière étape.

Les méthodes géométriques sont performantes lorsqu'elles sont faites manuellement, grâce aux capacités d'analyse globale du cerveau : il est simple et rapide de trouver un point de départ bien placé, et d'ajuster l'écartement du compas. mais cela devient fastidieux si de nombreux points sont proches du cercle final : il devient difficile de savoir quel sera le meilleur point B et F, il faut donc essayer plusieurs possibilités à chaque étape.

Si l'on automatise la méthode, alors : la recherche du centre initial C0 consiste à trouver le minimum et le maximum de l'abscisse et de l'ordonnée et de prendre la moyenne de ces extrêmes, c'est une étape en O() ; la recherche du point A nécessite de tester les points, c'est donc une étape en O() ; la recherche du point B nécessite de tester – 1 points autres points, c'est donc une étape en O() ; pour trouver le point F, il faut essayer les – 2 points restant, mais il faut à chaque fois vérifier que tous les – 3 autres points sont dans le cercle ; c'est l'étape limitante, elle est en O(n2). La performance automatisée est meilleure que pour l'algorithme d'essai-erreur, mais encore relativement médiocre, de l'ordre de O(2).

Algorithme de Chrystal

400px|Application de l'algorithme de Chrystal au cercle minimum

En 1885, le professeur M. Chrystal fait remarquer que le cercle minimum est entièrement déterminé par l'enveloppe convexe des points expérimentaux. Cela permet donc de réduire la recherche aux points de l'enveloppe convexe ( ≤ ), mais ajoute une étape de recherche de l'enveloppe convexe. Les algorithmes de recherche d'enveloppe convexe sont typiquement en O( log ) ou en O() ; la recherche manuelle est simple et rapide.

Considérons un côté [DE] du polygone (en rouge ci-contre) et les deux demi-plans délimités par la droite (DE) portant ce côté. Par définition de la convexité, la totalité du polygone est située dans un des demi-plan. On peut voir ce demi-plan comme un cercle de rayon infini et passant par D et par E. Alors on diminue le rayon du cercle jusqu'à ce que [DE] soit un diamètre, auquel cas nous avons obtenu le cercle minimum, ou bien le cercle passe par un troisième point expérimental, nommé F ; nous avons alors deux possibilités : soit le triangle DEF est acutangle (ou rectangle), nous avons alors trouvé le cercle minimum,