|
Problème du plus grand cercle vide Cet article est une ébauche concernant les mathématiques. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.  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. ApplicationsLe 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 (le cercle circonscrit du triangle ainsi formé), 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 :
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 Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ? Notes et références
Voir aussiArticles connexesLien externe(en) Largest Empty Circle Problem, Rashid Bin Muhammad, université d'État de Kent (États-Unis) |
