Problème du plus grand cercle vide

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le cercle en pointillé est le contour de la plus grande sphère vide dans l'empilement de sphères compact. Cela correspond au plus grand cercle vide dans le plan violet.

Le problème du plus grand cercle vide consiste, pour une région du plan, à trouver le plus grand cercle ne contenant aucun obstacle. Un obstacle est un sous-ensemble du plan, une « zone d'exclusion ».

Un problème restreint consiste à considérer des obstacles ponctuels. Le problème revient donc à trouver, pour un ensemble fini S de points du plan, le cercle le plus grand ne contenant aucun point de S et dont le centre se trouve dans l'enveloppe convexe de S.

Ce problème peut s'étendre dans un espace à trois dimensions, le problème de la plus grande sphère vide voire à n dimensions (n > 3), le problème de la plus grande hypersphère vide.

La solution de ce problème n'est pas nécessairement unique.

Applications[modifier | modifier le code]

Le centre du cercle est le point le plus éloigné des points de S, tout en restant dans le territoire délimité.

En termes d'aménagement du territoire, et en particulier d'emplacement d'une installation (facility location), les obstacles peuvent être des habitations, et le centre du cercle peut correspondre à l'emplacement d'un site nuisible que l'on veut le plus loin des habitations. Le site nuisible peut être par exemple un site industriel dans lequel un accident pourrait être dangereux pour la population (installation Seveso, installation nucléaire), ou bien source de nuisance (bruit, odeur). À l'inverse, les obstacles peuvent être des zones de nuisances, et le centre du plus grand cercle vide est alors l'endroit le plus sûr.

Cela suppose que la nuisance a une propagation isotrope, ce qui peut ne pas être le cas (la pollution d'un cours d'eau suit le courant, une pollution de l'air suit les vents).

Le problème peut aussi consister à choisir l'implantation d'une installation dans la région la moins bien desservie (problème de continuité territoriale, de couverture réseau), ou bien dans la région où il y aura le moins de concurrence. Les obstacles sont alors des zones de « bienfait » et non de nuisances.

La recherche de l'interstice le plus grand dans un empilement de sphères est un problème de plus grande sphère vide, les obstacles étant les sphères déjà présentes. Cela peut par exemple servir à déterminer les sites interstitiels les plus grands dans une maille atomique.

Algorithmes en deux dimensions[modifier | modifier le code]

Recherche du plus grand cercle vide avec le diagramme de Voronoï (deux solutions)

Jusqu'en 1975, on disposait d'un algorithme en O(n3)[1].

Shamos et Hoey[2] ont proposé un algorithme en O(n log n) utilisant les diagrammes de Voronoï.

En effet, on a deux configurations possibles :

  • soit le centre du cercle est à l'intérieur strict de l'enveloppe convexe ; dans ce cas-là, le cercle passe par trois points de l'ensemble S, il est donc sur un sommet du diagramme de Voronoï ;
  • soit le centre du cercle est sur l'enveloppe convexe ; dans ce cas-là, il passe par deux points de S, il est donc à l'intersection de l'enveloppe convexe et d'une arête du diagramme de Voronoï ; le cercle se trouve sur la médiatrice des points définissant l'arête.

La détermination des cercles circonscrits aux triangle correspondant aux sommets de Voronoï est une recherche en O(n). La détermination des intersections des arêtes de l'enveloppe convexe et du diagramme de Voronoï est aussi en O(n). Finalement, l'étape limitante est la construction du diagramme de Voronoï, qui est en O(n log n).

En dimension trois et plus[modifier | modifier le code]

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

  1. B. Dasarathy et Lee J. White, « On some maximin location of classifier problems: theory and algorithms », dans ACM Computer Science Conference, Washington DC,‎ février 1975, non publié ; B. Dasarathy et Lee J. White, « A Maxmin Location Problem », Operations Research, vol. 28, no 6,‎ 1980 (DOI 10.1287/opre.28.6.1385)
  2. (en) Michael Ian Shamos, Computational Geometry : thèse de doctorat, université Yale,‎ 1975
    (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

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Largest Empty Circle Problem, Rashid Bin Muhammad, université d'État de Kent (États-Unis)