Problème du plus grand cercle vide
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
Le centre du cercle est le point le plus éloigné des points de S, tout en restant dans le territoire délimité. C'est par exemple la notion de point Nemo, le point de l'océan le plus éloigné des terres.
En matière 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 » (lieu fournissant un service, un bien) 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
L'algorithme naïf consiste à tester les cercles passant par trois points non alignés, ainsi que les cercles passant par deux points (qui en forment le diamètre), et à regarder quels sont les cercles vides, pour pouvoir choisir le plus grand. 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).
Notes et références
- B. Dasarathy et Lee J. White, « On some maximin location of classifier problems: theory and algorithms », dans ACM Computer Science Conference, Washington DC, , non publié ; B. Dasarathy et Lee J. White, « A Maxmin Location Problem », Operations Research, vol. 28, no 6, , p. 1385-1401 (DOI 10.1287/opre.28.6.1385)
- (en) Michael Ian Shamos, Computational Geometry : thèse de doctorat, université Yale,
(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, (lire en ligne), p. 151-162
Voir aussi
Articles connexes
Lien externe
(en) Largest Empty Circle Problem, Rashid Bin Muhammad, université d'État de Kent (États-Unis)
Portail des mathématiques 
Portail de l'informatique théorique