# Problème du cercle minimum

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 :
   « 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 donné de points du plan. »
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 (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) ; le centre du cercle minimum est l'emplacement qui permet d'avoir le trajet de longueur maximale le plus court — c'est la formulation (P$_2$) ci-dessus — ; 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 un 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 ;
** 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 X du plan euclidien P, 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 M, associe la borne supérieure des distances de M aux points de X, est continue (car 1-lipschitzienne) et tend vers +∞ quand M s'éloigne à l'infini, donc elle atteint son minimum r, en un point C : $r=\min _{M\in P}\sup _{A\in X}\;\|x-a_{i}\|.$
Le disque ${\mathcal {D}}(C,r)$ de centre C et de rayon r est alors un disque englobant de rayon minimum, et le cercle de centre C et de rayon r ${\mathcal {C}}(C,r)$ un cercle englobant de rayon minimum.
L'unicité de C 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 : $r\leqslant {\frac {d_{X}}{\sqrt {3}}}$ où $d_{X}=\sup _{A,B\in X}AB$ est le diamètre de X.

## Cas triviaux

* Cas triviaux
* Singleton {A}.
* Paire {A$_1$, A$_2$}.
* Triplet {A$_1$, A$_2$, A$_3$} formant un triangle acutangle.
* Triplet formant un triangle obtusangle en A$_2$.
* L'ensemble X 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 X est une paire de points distincts {A$_1$, A$_2$} : il s'agit du cercle de diamètre [A$_1$A$_2$] ;
* 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 {A$_1$, A$_2$, A$_3$} : soit c'est un des cercles de diamètre [A$_1$A$_2$], [A$_2$A$_3$] ou [A$_3$A$_1$], 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 n points (n > 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 X ; il est très peu probable — voire impossible dans un cas réel — que quatre points ou plus soient sur le cercle. 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 n points, appelés « points expérimentaux », et notés A$_1$(n$_1$, n$_1$), …, A$_n$(x$_n$, y$_n$).

### 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 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(n$^4$).
C'est un algorithme simple à mettre en œuvre de manière automatisée, mais il est peu performant.

### Algorithme géométrique

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.
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 C$_0$ 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 C$_0$. Le cercle de centre C$_0$ et de rayon C$_0$A, donc passant par A, contient tous les points.
* Commençons par tracer un cercle initial Γ$_0$ comme déterminé précédemment (centre C$_0$, rayon C$_0$A).
* 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 C$_1$, on repère le point B susceptible de convenir, et on utilise le fait que [AB] est une corde. C$_1$ est donc l'intersection de la médiatrice de [AB] et de [C$_0$A].
* 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 C$_0$ 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(n$^2$).
La performance automatisée est meilleure que pour l'algorithme d'essai-erreur, mais encore relativement médiocre, de l'ordre de O(n$^2$).

### Algorithme de Chrystal

* Application de l'algorithme de Chrystal. L'enveloppe convexe est en bleu.
* 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.
* On choisit donc 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.
* 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. Cela permet donc de réduire la recherche aux m points de l'enveloppe convexe (m ≤ n), 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 côté 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 à :
* Déterminer l'enveloppe convexe (H$_i$)$_{1≤i≤m}$.
* Prendre un côté arbitraire [H$_i$H$_j$] de l'enveloppe convexe (par exemple [H$_1$H$_2$] 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 H$_k$ :
** si cet angle est droit ou obtus, le cercle minimum est le cercle ayant le côté pour diamètre [H$_i$H$_j$] ;
** si les trois angles sont aigus, le cercle minimum est le cercle circonscrit au triangle ;
** si le triangle H$_i$H$_j$H$_k$ est obtus en H$_i$, alors recommencer l'étape 3 en considérant le segment [H$_j$H$_k$] ; s'il est obtus en H$_j$, alors recommencer l'étape 3 en considérant le segment [H$_i$H$_k$].
Dans le pire des cas, il essayer ½m(m – 1) triangles. On a donc une complexité en O(m$^2$).
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

* Algorithme de Shamos et Hoey.
* Détermination de l'enveloppe convexe (points de couleur) et du diagramme de Voronoï des points les plus éloignés.
* Détermination de la paire la plus éloignée et essai du cercle dont elle est le diamètre.
* Détermination des triplets les plus éloignés, et essai des cercles circonscrits correspondant.
En 1975, Shamos et Hoey 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 :
* Construire le diagramme de Voronoï des points les plus éloignés pour S.
* Pour chaque segment du diagramme, déterminer la distance des points correspondant au segment. Retenir le segment correspondant à la distance la plus grande, segment correspondant à la paire de points {A, B}, et vérifier si le cercle de diamètre [AB] englobe tous les points ; si c'est le cas, c'est le cercle minimum.
* 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

Le problème peut être résolu en O(n) opérations par l'algorithme de Megiddo (1983). 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

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)$^2$n 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

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 A$_i$ vaut
    $d_{i}^{2}(x)=(x_{i}-x)^{2}+y_{i}^{2}$
et le carré du rayon du cercle minimum de centre (x, 0) est
    $g(x)=\max _{1\leqslant i\leqslant n}d_{i}^{2}(x).$
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 :
    $\mathrm {I} (x)=\{i;d_{i}^{2}(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 A$_i$ et A$_j$ distincts. Si d$_i$$^2$(x$^*$) < d$_j$$^2$(x$^*$), alors on peut éliminer le point i de la recherche ; et vice versa, si d$_i$$^2$(x$^*$) > d$_j$$^2$(x$^*$), alors on peut éliminer le point j.
Dans le cas particulier où les points ont la même abscisse, x$_i$ = x$_j$, alors on peut éliminer celui qui est le plus proche de l'axe des x. Par exemple, si
    $y_{i}^{2}<y_{j}^{2}$
alors on élimine le point i et l'on ne garde que le point j.
Dans le cas général, on a x$_i$ ≠ x$_j$. On s'intéresse au signe de la différence d$_j$$^2$(x) – d$_i$$^2$(x) :
    $d_{j}^{2}(x)-d_{i}^{2}(x)\geqslant 0\Longleftrightarrow 2(x_{j}-x_{i})x\geqslant x_{i}^{2}-x_{j}^{2}+y_{i}^{2}-y_{j}^{2}$
et ainsi :
* si (x$_j$ – x$_i$) > 0, alors x ≥ (x$_i$$^2$ – x$_j$$^2$ + y$_i$$^2$ – y$_j$$^2$)/2/(x$_j$ – x$_i$) ;
* si (x$_j$ – x$_i$) < 0, alors x ≤ (x$_i$$^2$ – x$_j$$^2$ + y$_i$$^2$ – y$_j$$^2$)/2/(x$_j$ – x$_i$) ;
Il y a ainsi une valeur critique x$_{criti,j}$ telle que
    $d_{i}^{2}(x_{\mathrm {crit} \ i,j})=d_{j}^{2}(x_{\mathrm {crit} \ 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 [A$_i$A$_j$] et (y = 0), puisque le point (x$_{criti,j}$, 0) est à équidistance de A$_i$ et de A$_j$.
On a ainsi quatre possibilités.
Signe de $d_{j}^{2}(x)-d_{i}^{2}(x)$ :
| | | signe de (x$_j$ – x$_i$) | signe de (x$_j$ – x$_i$) |
| signe de (x – x$_{criti,j}$) | + | + | – |
| signe de (x – x$_{criti,j}$) | – | – | + |
ou bien encore
Comparaison des carrés des distances :
| | x$_j$ > x$_i$ | x$_j$ < x$_i$ |
| x > x$_{criti,j}$ | d$_j$$^2$(x) > d$_i$$^2$(x) | d$_j$$^2$(x) < d$_i$$^2$(x) |
| x < x$_{criti,j}$ | d$_j$$^2$(x) < d$_i$$^2$(x) | d$_j$$^2$(x) > d$_i$$^2$(x) |
Regroupons les points expérimentaux arbitrairement par deux, par exemple {A$_1$ ; A$_2$}, {A$_3$ ; A$_4$}, …, {A$_i$ ; A$_{i+1}$} avec i impair. Déterminons la médiane des valeurs critiques x$_{criti,i+1}$ :
    $x_{\mathrm {m} }=\mathrm {mediane} \{x_{\mathrm {crit} \ i,i+1}\}.$
Il existe des algorithmes de recherche de la médiane en O(n).
Supposons alors que la médiane se trouve au-dessus de la solution contrainte
    $x_{\mathrm {m} }\geqslant x^{*}$
cela signifie que dans la moitié des cas on a
    $x_{\mathrm {crit} \ i,i+1}\geqslant x_{\mathrm {m} }(\geqslant 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 x$_{i+1}$ – x$_i$. De même, si x$_m$ ≤ x$^*$, on s'intéresse à la moitié des paires telles que x$_{criti,i+1}$ ≤ x$_m$.
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 à x$_m$ 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 points à condition de savoir si x$^*$ est au-dessus ou en dessous de la médiane x$_m$. 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 à x$_m$.
En effet : considérons l'ensemble des points situés sur le cercle minimum centré sur la médiane :
    $\mathrm {I} (x_{\mathrm {m} }){=}\{i;d_{i}^{2}(x)=g(x_{\mathrm {m} })\}.$
Si pour tout i de I, on a
* x$_m$ < x$_i$, alors x$_m$ < x$^*$ ;
* x$_m$ > x$_i$, alors x$_m$ > x$^*$ ;
* sinon, x$_m$ = 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 :
* Pour chaque paire {A$_i$ ; A$_{i+1}$} (i impair), on détermine la valeur critique x$_{criti,i+1}$.
* On détermine la médiane x$_m$ des x$_{criti,i+1}$.
* On calcule g(x$_m$), on détermine l'ensemble I, et à partir de là, on sait si x$_m$ < x$^*$, x$_m$ > x$^*$ ou si x$_m$ = x$^*$.
* 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 A$_i$, soit A$_{i+1}$, selon le signe de x$_{i+1}$ – x$_i$.

#### Élagage dans le cas non contraint

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 :
    D$_i$$^2$(x, y) = (x$_i$ – x)$^2$ + (y$_i$ – y)$^2$
et l'on définit la fonction qui donne le rayon du cercle minimum de centre (x, y)
    ƒ(x, y) = max{D$_i$$^2$(x, y)}$_{1≤i≤n}$.
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) = min$_x$ ƒ(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, y$_c$, correspond au minimum de h(y) :
    min h(y) = h(y$_c$).
Du fait de la convexité de h, on peut connaître le signe de y$_c$ 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$^*$ = x$_i$ et donc y$_c$ est du même signe que y$_i$ ;
* si I(x$^*$) est une paire, I(x$^*$) = {i ; j}, alors x$^*$ est sur la médiatrice de [A$_i$A$_j$] et donc y$_c$ est du même signe que l'ordonnée du milieu de [A$_i$A$_j$] ; y$_i$ est du signe de ½(y$_i$ + y$_j$) ;
* 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 y$_c$ = 0,
** sinon, il existe un segment [A$_i$A$_j$] tel que ƒ(x, y) diminue lorsque l'on va du centre (x$^*$, 0) vers le milieu de [A$_i$A$_j$] (donc en se déplaçant selon la médiatrice) ; y$_i$ est du signe de ½(y$_i$ + y$_j$).
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 y$_c$ sinon —, la détermination du signe de y$_c$ 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 (x$_c$, y$_c$). 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

* On groupe les points arbitrairement par paire ; le plus simple est de former les paires {A$_i$ ; A$_{i+1}$} avec i impair, ce que l'on peut encore écrire {A$_{2i–1}$ ; A$_{2i}$} avec 1 ≤ i ≤ n/2. On appelle L$_i$ la médiatrice de [A$_{2i–1}$A$_{2i}$], et α$_i$ l'angle qu'elle fait avec l'axe des x (exprimé dans l'intervalle [–π/2 ; π/2]).
* On recherche la médiane α$_m$ de ces angles : α$_m$ = médiane {α$_i$, 1 ≤ i ≤ n/2}. On regroupe les médiatrices L$_i$ 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.
* On fait des paires de lignes {L$_i$ ; L$_j$}, appartenant chacune à un sous-ensemble différent. Dans le cas général, les lignes sont sécantes et l'on note (x$_{ij}$, y$_{ij}$) le point d'intersection. On a n/4 points d'intersection.
* On détermine la médiane y$_m$ des y$_{ij}$. On prend comme référence la droite (y = y$_m$) ; 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.
* De même avec x$_m$ des x$_{ij}$, 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.
* Pour chacun des n/16 points (x$_{ij}$, y$_{ij}$) de ce quart de plan, on peut sélectionner une des deux droites (L$_i$ ou L$_j$) : 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.
* Et pour chacune des n/16 droites ainsi sélectionnées, 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.

### Algorithme de Welzl

En 1991, Emo Welzl (en) a proposé un algorithme de complexité linéaire (en O(n)). C'est une démarche de programmation linéaire utilisant l'algorithme de Raimund Seidel (en). C'est un algorithme récursif.
L'algorithme considère trois ensembles : S est l'ensemble des points non testés, Q est l'ensemble des points testés situés sur le cercle minimum, P est l'ensemble des points situés strictement à l'intérieur du cercle. Initialement, S contient tous les points, P et Q sont vides.
À une étape donnée, on détermine le cercle minimum de Q : seuls les points sur le cercle restent dans Q, les autres sont transférés dans P.
Le point suivant r est choisi aléatoirement dans S et lui en est retiré :
* si r se trouve à l'intérieur du cercle actuel, alors il est inclus dans P ;
* sinon, le cercle est remplacé par un appel récursif aux ensembles P et Q + r.
La probabilité que le ie point génère un appel récursif varie en 1/i.

## Extension aux dimensions supérieures

Dans le problème de la sphère minimum dans un espace de dimension trois :
* 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 trois points, ils ne sont pas alignés et le plan qu'ils définissent coupe la sphère en deux hémisphères égales ; l'intersection de ce plan et de la sphère est le cercle minimum dans ce plan ;
** si elle passe par quatre points, ceux-ci sont sauf exception non-coplanaires et 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 à un hémisphère, et que le sommet du tétraèdre n'appartenant pas à la face est sur cette grande calotte.
On pourra consulter les contributions de Megiddo (1983) et de Dyer (1986) pour les dimensions supérieures.