Problème du plus grand cercle vide

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.

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

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(n³)[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).