Problème du cercle minimum

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Cercles minima encerclant des ensembles de points.

Le problème du cercle minimum consiste à trouver le cercle le plus petit contenant un ensemble de points d'un plan. On peut étendre ce problème à trois dimensions, il s'agit alors de trouver la sphère minimum contenant les points, voire à d dimensions (d > 3), il s'agit alors d'hypersphères.

Historique[modifier | modifier le code]

Le problème de recherche du cercle minimum a été soulevé par Sylvester en 1857[1] :

« It is required to find the least circle which shall contain a given set of points in the plane. »

soit en français

« Il faut trouver le plus petit cercle qui contient un ensemble de points du plan. »

Formulations mathématiques du problème[modifier | modifier le code]

Le problème du cercle minimal est un problème d'optimisation qui peut s'exprimer de différentes manières. On note a_i, i\in[\![1,n]\!], les points que le disque de rayon minimal doit recouvrir, englober. On note x le centre du disque minimal et r son rayon.

Dans la première formulation, on cherche à minimiser le rayon r, en imposant que la boule fermée \mathrm{B}(x,r) de centre x et de rayon r doit contenir les points a_i :


(\mathrm{P}_1)\qquad
\left\{\begin{array}{l}
\inf\;r\\
\|x-a_i\|\leqslant r
\end{array}\right.
\qquad\quad\mbox{ou}\qquad\quad
(\mathrm{P}_1')\qquad
\left\{\begin{array}{l}
\inf\;r\\
\|x-a_i\|^2\leqslant r^2,
\end{array}\right.

\|\cdot\| est la norme euclidienne. La formulation (P'1) est la version différentiable de la formulation (P1).

On peut éliminer le rayon du problème en prenant la formulation suivante, qui est équivalente à la formulation (P1) :


(\mathrm{P}_2)\qquad\inf_x\max_{1\leqslant i \leqslant n}\;\|x-a_i\|.

Applications[modifier | modifier le code]

La résolution de ce problème peut servir :

  • à déterminer l'emplacement optimal d'une installation, d'une ressource servant à plusieurs clients (facility location), 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 » (post office problem)[2] ; 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-dessus[3] — ; 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 n points expérimentaux (états dont les valeurs des paramètres sont des points dans une espace à m 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.

Cas triviaux[modifier | modifier le code]

  • 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 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, 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 n points (n > 3).

Propriétés générales[modifier | modifier le code]

Le cercle minimum existe et est unique.

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 cercle[4]. 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).

Dans le problème de la sphère minimum dans un espace à trois dimensions[5] :

  • la sphère minimum est unique ;
  • elle passe par deux, trois ou quatre points de l'ensemble ;
    • si elle passe par deux points et uniquement deux, ceux-ci forment un diamètre de la sphère,
    • si elle passe par quatre points, ceux-ci forment un tétraèdre acutangle, c'est-à-dire qu'une face du tétraèdre sépare la sphère en deux calottes dont une est supérieure à une hémisphère, et que le sommet du tétraèdre n'appartenant pas à la face est sur cette grande calotte.

Algorithmes[modifier | modifier le code]

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

Recherche par essai-erreur[modifier | modifier le code]

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 n(n - 1)/2 (voir Combinaison (mathématiques)) ;
  • les cercles circonscrits aux triangles formés par les points pris trois par trois — il y en a n(n - 1)(n - 2)/6 ;

et à trouver le plus petit de ces cercles contenant tous les points — il faut donc, pour chaque disque, vérifier si les n - 2 ou n - 3 points restants sont dans le disque.

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

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

Algorithme géométrique[modifier | modifier le code]

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 points[6].

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.

  1. Commençons par tracer un cercle initial Γ0 comme déterminé précédemment (centre C0, rayon C0A).
  2. 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].
  3. 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 point 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(n) ;
  • la recherche du point A nécessite de tester les n points, c'est donc une étape en O(n) ;
  • la recherche du point B nécessite de tester n - 1 points autres points, c'est donc une étape en O(n) ;
  • pour trouver le point F, il faut essayer les n - 2 points restant, mais il faut à chaque fois vérifier que tous les n - 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(n2).

Algorithme de Chrystal[modifier | modifier le code]

Applicaiton de l'algorithme de Chrystal. L'enveloppe convexe est en bleu.
  1. Le côté choisi, en rouge, génère deux triangles, en vert. Le triangle ayant l'angle opposé le plus petit (trait plein) a un angle obtus adjacent au segment.
  2. On choisit onc le côté opposé à l'angle obtus (en rouge). On construit de même deux triangles (en vert). Le triangle ayant l'angle opposé le plus petit (trait plein) est acutangle.
  3. On construit le cercle circonscrit à ce triangle.

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[5]. Cela permet donc de réduire la recherche aux m points de l'enveloppe convexe (mn), mais ajoute une étape de recherche de l'enveloppe convexe. Les algorithmes de recherche d'enveloppe convexe sont typiquement en O(n log n) ou en O(nm) ; 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,
    • soit le triangle DEF est obtusangle, l'angle obtus est alors nécessairement en D ou en E (si le triangle est obtus en F, alors F est contenu dans le cercle de diamètre [DE]) ; dans ce cas, nous considérons le côté opposé à l'angle obtus du triangle, et nous recommençons la recherche.
      Autre manière de voir : l'arc de cercle libre (ne contenant aucun point) intercepté par le coté opposé à l'angle obtus est plus grand qu'un demi-périmètre ; tant que l'on a un arc libre de plus d'un demi-périmètre, le cercle n'est pas minimum.

Concrètement, cela revient à :

  1. Déterminer l'enveloppe convexe (Hi)1 ≤ im.
  2. Prendre un côté arbitraire [HiHj] de l'enveloppe convexe (par exemple [H1H2] si les sommets sont adjacents), et regarder les triangles formés par ce côté et chacun des m - 2 autres sommets. Garder le sommet donnant le plus petit angle opposé, appelons-le Hk :
    • si cet angle est droit ou obtus, le cercle minimum est le cercle ayant le côté pour diamètre [HiHj] ;
    • si les trois angles sont aigus, le cercle minimum est le cercle circonscrit au triangle ;
    • si le triangle HiHjHk est obtus en Hi, alors recommencer l'étape 3 en considérant le segment [HjHk] ; s'il est obtus en Hj, alors recommencer l'étape 3 en considérant le segment [HiHk].

Dans le pire des cas, il essayer ½m(m - 1) triangles. On a donc une complexité en O(m2).

Notons que pour le problème de la sphère minimum dans un espace à trois dimensions, il suffit de remplacer le triangle acutangle par un tétraèdre acutangle.

Algorithme de Shamos et Hoey[modifier | modifier le code]

Algorithme de Shamos et Hoey.
  1. Détermination de l'enveloppe convexe (points de couleur) et du diagramme de Voronoï des points les plus éloignés.
  2. Détermination de la paire la plus éloignée et essai du cercle dont elle est le diamètre.
  3. Détermination des triplets les plus éloignés, et essai des cercles circonscrits correspondant.

En 1975, Shamos et Hoey[7] ont proposé un algorithme de complexité O(n log n) utilisant le diagramme de Voronoï des points les plus éloignés.

On appelle S l'ensemble des points de l'enveloppe convexe des points expérimentaux.

Si le cercle minimum est défini par deux points, alors ces points sont plus éloignés du centre C de ce cercle que les autres points de S. Donc, le centre est plus loin de ces deux points que de n'importe quel autre de S. Il se trouve donc dans deux cellules du diagramme de Voronoï des points les plus éloignés, il est donc sur le segment séparant deux cellules.

Si le cercle minimum est défini par trois points, alors ces points sont plus éloignés du centre C du cercle que les autres points de S. Donc, le centre est plus loin de ces trois points que de n'importe quel autre de S. Donc, C fait partie de trois cellules du diagramme de Voronoï des points les plus éloignés, il est donc sur un nœud triple.

La recherche du cercle minimum consiste ici à rechercher son centre parmi un ensemble de points déterminés par le diagramme de Voronoï des points les plus éloignés. L'algorithme est donc le suivant :

  1. Construire le diagramme de Voronoï des points les plus éloignés pour S.
  2. Pour chaque segment du diagramme, déterminer la distance des points correspondant au segment. Retenir le segment le plus grand, [AB] et vérifier si le cercle de diamètre [AB] englobe tous les points ; si c'est le cas, c'est le cercle minimum.
  3. Sinon, prendre chaque nœud du diagramme, et vérifier pour chaque cercle s'il contient tous les points de S. Si c'est le cas et que le triangle est actusangle, c'est le cercle minimum.

Algorithme de Megiddo[modifier | modifier le code]

Le problème peut être résolu en O(n) opérations par l'algorithme de Megiddo (1983[8]). Il est fondé sur le fait que le cercle minimum passe par deux ou trois points expérimentaux, donc qu'il suffit de sélectionner les deux ou trois points pertinents pour avoir le résultat. C'est un algorithme performant, mais qui n'est pas évident. En effet, il faut éliminer des points qui ne contribuent pas à la construction du cercle, sans connaître ledit cercle.

Description générale[modifier | modifier le code]

Tout d'abord, les propriétés du problème permettent de déterminer un quart de plan dans lequel on est sûr que le centre du cercle se trouve.

Si deux segments de droite sont des cordes du cercle, alors le centre du cercle se trouve à l'intersection des médiatrices des deux cordes. La première étape consiste donc à grouper les points deux par deux — ce sont les cordes potentielles —, puis à regrouper ces segments deux par deux. On regarde les paires de segments dont les médiatrices se coupent pas dans le quart de plan opposé au quart de plan où se trouve le centre du cercle.

Pour chaque paire de segments, au moins un des segments n'est pas une corde. Puisque l'intersection n'est pas dans le quart de plan où se trouve le centre, c'est qu'une des médiatrices ne passe pas par ce quart de plan : on est sûr que le segment correspondant n'est pas une corde. Puis, sur cette corde-là, on détermine un des points dont on est sûr qu'il n'est pas sur le cercle : c'est celui qui est le plus proche du quart de plan où se trouve le centre (puisqu'il est nécessairement à l'intérieur du cercle).

Il s'agit d'un algorithme d'élagage (prune and search) : à chaque étape, on élimine au moins 1/16 des points, jusqu'à ne retenir que 3 points. La première étape nécessite donc n opérations, la suivante (1 - 1/16)n = (15/16)n opérations, la troisième (15/16)2n opérations… soit au total environ n Σ(15/16)i = 16n opérations (il s'agit d'une série géométrique de raison 15/16).

Élagage dans le cas du problème contraint[modifier | modifier le code]

Megiddo commence par s'intéresser à un problème contraint : trouvons le cercle minimum dont le centre est sur l'axe des x, c'est-à-dire la droite horizontale d'équation (y = 0). Ce problème est plus simple que le problème initial, et permet de mettre en place la méthode.

Un point de cette droite a pour coordonnées (x, 0), le carré de la distance de ce point à un point expérimental Ai vaut

di2(x) = (xi - x)2 + yi2

et le carré du rayon du cercle minimum de centre (x, 0) est

g(x) = max{di2(x)}1 ≤ in.

La solution x* du problème contraint est le minimum de g :

x* = min(g(x)).

Notons I(x) l'ensemble des points situés sur le cercle minimum de centre (x, 0), donc de rayon g(x). On se contente en fait de l'ensemble des indices, on a :

I(x) = {i ; di2(x) = g(x)}

cet ensemble n'est pas vide, puisqu'il est constitué des points les plus éloignés de (x, 0). Sauf construction particulière, il s'agit en général d'un singleton. Dans le cas de la solution du problème contraint, I(x*), il s'agit en général d'un singleton ou d'une paire.

Prenons une paire de points expérimentaux Ai et Aj distincts. Si di2(x*) < dj2(x*), alors on peut éliminer le point i de la recherche ; et vice versa, si di2(x*) > dj2(x*), alors on peut éliminer le point j.

Dans le cas particulier où les points ont la même abscisse, xi = xj, alors on peut éliminer celui qui est le plus proche de l'axe des x. Par exemple, si

yi2 < yj2

alors on élimine le point i et l'on ne garde que le point j.

Dans le cas général, on a xixj. On s'intéresse au signe de la différence dj2(x) - di2(x) :

dj2(x) - di2(x) ≥ 0 ⇔ 2(xj - xi)xxi2 - xj2 + yi2 - yj2

et ainsi :

  • si (xj - xi) > 0, alors x ≥ (xi2 - xj2 + yi2 - yj2)/2/(xj - xi) ;
  • si (xj - xi) < 0, alors x ≤ (xi2 - xj2 + yi2 - yj2)/2/(xj - xi) ;

Il y a ainsi une valeur critique xcrit i, j telle que

di2(xcrit i, j) = dj2(xcrit i, j)

et cette valeur vaut

x_{\mathrm{crit}\ i, j} = \frac{x_i^2 - x_j^2 + y_i^2 - y_j^2}{2(x_j - x_i)}

notons que c'est l'intersection entre la médiatrice de [AiAj] et (y = 0), puisque le point (xcrit i, j, 0) est à équidistance de Ai et de Aj.

On a ainsi quatre possibilités.

Signe de dj2(x) - di2(x)
 
signe de (xj - xi)
+ -
signe de
(x - xcrit i, j)
+ + -
- - +

ou bien encore

Comparaison des carrés des distances
xj > xi xj < xi
x > xcrit i, j
 
dj2(x) > di2(x) dj2(x) < di2(x)
x < xcrit i, j
 
dj2(x) < di2(x) dj2(x) > di2(x)

Regroupons les points expérimentaux arbitrairement par deux, par exemple {A1 ; A2}, {A3 ; A4}, …, {Ai ; Ai + 1} avec i impair. Déterminons la médiane des valeurs critiques xcrit i, i + 1 :

xm = médiane{xcrit i, i + 1}.

Il existe des algorithme de recherche de la médiane en O(n).

Supposons alors que la médiane se trouve au-dessus de la solution contrainte

xmx*

cela signifie que dans la moitié des cas on a

xcrit i, i + 1xm (> x*)

et pour ces paires-là, on peut aisément éliminer la moitié des points de la recherche — le point de la paire le plus proche du centre (x*, 0) — en fonction du signe de xi + 1 - xi. De même, si xmx*, on s'intéresse à la moitié des paires telles que xcrit i, i + 1xm.

Si l'on a n points, alors on a n/2 paires, et pour au moins la moitié de ces paires (soit n/4 paires), on peut éliminer un des points.

L'avantage de se référer à xm plutôt qu'à x* est que l'on travaille sur une quantité connue et facile à calculer — x* est initialement inconnu.

On peut donc éliminer un quart des point à condition de savoir si x* est au-dessus ou en dessous de la médiane xm. C'est intéressant, car nous n'avons pas à connaître la valeur de x* — la solution, donc — pour savoir si elle est supérieure ou inférieure à xm.

En effet : considérons l'ensemble des points situés sur le cercle minimum centré sur la médiane :

I(xm) = {i ; di2(x) = g(xm)}.

Si pour tout i de I, on a

  • xm < xi, alors xm < x* ;
  • xm > xi, alors xm > x* ;
  • sinon, xm = x* ;

rappelons que I est en général d'un singleton.

Donc, on peut éliminer un quart des points de la manière suivante :

  1. Pour chaque paire {Ai ; Ai + 1} (i impair), on détermine la valeur critique xcrit i, i + 1.
  2. On détermine la médiane xm des xcrit i, i + 1.
  3. On calcule g(xm), on détermine l'ensemble I, et à partir de là, on sait si xm < x*, xm > x* ou si xm = x*.
  4. Selon le cas, on se place au-dessus ou en dessous de la médiane, et pour chaque i impair dans le sous-ensemble considéré, on peut éliminer de la recherche soit Ai, soit Ai + 1, selon le signe de xi + 1 - xi.

Élagage dans le cas non contraint[modifier | modifier le code]

Dans le cas non contraint — le problème initial —, le carré de la distance du point expérimental i au point de coordonnées (x, y) vaut :

Di2(x, y) = (xi - x)2 + (yi - y)2

et l'on définit la fonction qui donne le rayon du cercle minimum de centre (x, y)

ƒ(x, y) = max{Di2(x, y)}1 ≤ in.

Cette fonction est convexe en x, en y, mais aussi en (x, y). Notons que l'on a

g(x) = ƒ(x, 0).

On définit la fonction

h(y) = minx ƒ(x, y).

La fonction h est elle aussi convexe. Notons que l'on a :

g(x*) = h(0).

L'ordonnée du centre du cercle minimum, yc, correspond au minimum de h(y) :

min h(y) = h(yc).

Du fait de la convexité de h, on peut connaître le signe de yc en regardant le comportement de h autour de 0, c'est-à-dire en considérant g(x*) :

  • si I(x*) est un singleton, I(x*) = {i}, alors x* = xi et donc yc est du même signe que yi ;
  • si I(x*) est une paire, I(x*) = {i ; j}, alors x* est sur la médiatrice de [AiAj] et donc yc est du même signe que l'ordonnée du milieu de [AiAj] ; yi est du signe de ½(yi + yj) ;
  • s'il y a trois points ou plus dans I, alors
    • si le centre du cercle (x*, 0) est dans l'enveloppe convexe de ces points, on a yc = 0,
    • sinon, il existe un segment [AiAj] tel que ƒ(x, y) diminue lorsque l'on va du centre (x*, 0) vers le milieu de [AiAj] (donc en se déplaçant selon la médiatrice) ; yi est du signe de ½(yi + yj).

Dans les cas les plus complexes — déterminer si (x*, 0) est dans l'enveloppe convexe de I, ou bien recherche du segment déterminant le signe de yc sinon —, la détermination du signe de yc est une opération en O(n).

Nous avons considéré de manière particulière la droite (y = 0) comme référence, mais tout le travail peut être effectué pour une droite quelconque du plan.

Conclusion
Pour toute droite du plan, divisant le plan en deux demi-plans, nous sommes capable de déterminer dans quel demi-plan se trouve le centre du cercle minimum (xc, yc). La recherche de ce demi-plan est en O(n).
Si le centre se trouve sur la droite elle-même, alors nous avons la solution en résolvant le problème contraint.

Nous pouvons donc élaguer les points se trouvant du « mauvais côté » de la droite considérée.

Description de l'algorithme[modifier | modifier le code]

  1. On groupe les points arbitrairement par paire ; le plus simple est de former les paires {Ai ; Ai + 1} avec i impair, ce que l'on peut encore écrire {A2i - 1 ; A2i} avec 1 ≤ in/2. On appelle Li la médiatrice de [A2i - 1A2i], et αi l'angle qu'elle fait avec l'axe des x (exprimé dans l'intervalle [-π/2 ; π/2]).
  2. On recherche la médiane αm de ces angles : αm = médiane {αi, 1 ≤ in/2}. On regroupe les médiatrices Li en deux groupes : le sous-ensemble ayant un angle supérieur à la médiane, et le sous-ensemble ayant un angle inférieur à la médiane. Ce sont des sous-ensembles disjoints comprenant n/4 lignes chacun.
  3. On fait des paires de lignes {Li ; Lj}, appartenant chacune à un sous-ensemble différent. Dans le cas général, les lignes sont sécantes et l'on note (xij, yij) le point d'intersection. On a n/4 points d'intersection.
  4. On détermine la médiane ym des yij. On prend comme référence la droite (y = ym) ; elle délimite deux demi-plans. On détermine dans quel demi-plan se trouve le centre du cercle minimum, et l'on se place dans l'autre demi-plan.
  5. De même avec xm des xij, on délimite ainsi un quart de plan dans lequel ne se trouve pas le centre du cercle minimum. Ce quart de plan contient un quart des points d'intersection, donc n/16 points.
  6. Pour chacun des n/16 points (xij, yij) de ce quart de plan, on peut sélectionner une des deux droite (Li ou Lj) : en effet, une des droites, du fait de son angle, ne passe pas dans le quart de plan opposé (celui contenant le centre du cercle minimum), et ainsi, au moins un des points du segment ne peut pas être sur le cercle minimum[9].
  7. Et pour chacune des n/16 droites ainsi sélectionnée, on détermine de quel côté se trouve le centre du cercle minimum. Comme la droite est la médiatrice d'un segment, on élimine le point du segment qui se trouve du côté du centre du cercle minimum (le point le plus proche ne peut pas être sur le cercle).

On élimine ainsi n/16 points.

Extension aux dimensions supérieures[modifier | modifier le code]

On pourra consulter les contributions de Megiddo (1983[10]) et de Dyer (1986[11]).

Notes et références[modifier | modifier le code]

  1. (en) J. J. Sylvester, « A Question in the Geometry of Situation », Quarterly Journal of Pure and Applied Mathematics, vol. 1,‎ 1857, p. 79
  2. 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
  3. De 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 » x\in\R^n qui minimise la somme des distances aux points a_i :
    \min_{x\in\R^n}\,\left(\sum_{i=1}^m\|x-a_i\|\right).
    Pour en apprendre davantage, on pourra consulter la section 11.7 chez O. Güler, Foundations of Optimization, Springer, coll. « Graduate Texts in Mathematics »,‎ 2010 (ISBN 978-0-38734-431-7), chap. 258 et l'article de G. Xue et Y. Ye, « An efficient algorithm for minimizing a sum of Euclidean norms with applications », SIAM Journal on Optimization, no 7,‎ 1997, p. 1017-1036.
  4. Par « 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 \mathbb{D} dans \R, 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é.
  5. a et b M. Chrystal (trad. M. l'abbé Pautonnier), « Sur le problème de la construction du cercle minimum renfermant n points de données d'un plan », Bulletin de la S.M.F., Société mathématique de France,‎ 1885 (lire en ligne)
  6. Smallest Enclosing Circle Problem, Rashid Bin Muhammad, Université de l'État du Kent (États-Unis)
  7. (en) Michael Ian Shamos et Dan Hoey, « Closest-point problems », dans Proceeding of 16th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, IEEE Computer Society Press,‎ 1975 (lire en ligne), p. 151-162
  8. (en) Nimrod Megiddo, « Linear-time algorithms for linear programming in \R^3 and related problems », SIAM Journal on Computing (en), vol. 4,‎ 1983, p. 766-769 (DOI 10.1137/0212052, lire en ligne)
  9. rappelons que les médiatrices d'une corde d'un cercle passent par le centre du cercle
  10. (en) Nimrod Megiddo, « The weighted Euclidean 1-center problem », Mathematics of Operations Research, vol. 8,‎ 1983, p. 498-504
  11. (en) M.E. Dyer, « On a multidimensional search technique and its application to the Euclidean one-centre problem », SIAM Journal on Computing, vol. 15,‎ 1986, p. 725-738

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]