Problème des villages de Voronoi : trier, simplifier et trouver le plus petit voisinage
Le problème des villages de Voronoi vous demande de trouver la plus petite région de Voronoi sur une droite numérique. Commencez par trier les coordonnées, sautez les deux points extrêmes car ils s'étendent à l'infini, puis appliquez une formule : (voisin de droite − voisin de gauche) ÷ 2. La complexité temporelle globale est O(N log N).
Le problème des villages de Voronoi est un défi classique de programmation compétitive qui transforme une idée du monde réel — chaque maison se connecte à sa tour de téléphonie mobile la plus proche — en une énigme algorithmique claire sur une droite numérique unidimensionnelle. Maîtrisez les trois idées clés ci-dessous et vous pourrez le résoudre en moins de vingt lignes de code.
Qu’est-ce que le problème des villages de Voronoi ?
Le problème des villages de Voronoi est une tâche de programmation où N villages se trouvent à des coordonnées entières sur une route droite, chaque village « possède » chaque point sur la route plus proche de lui que de tout autre village, et votre tâche est de trouver la taille de la plus petite région de propriété. Un diagramme de Voronoi est la version générale en 2D de cette idée de partitionnement ; la version 1D réduit chaque région à un intervalle simple dont les limites sont les points médians entre les villages consécutifs.
Dans la version canonique du problème, cinq villages se trouvent aux coordonnées 16, 0, 10, 4 et 15. Les coordonnées peuvent varier de −1 000 000 000 à +1 000 000 000. Votre programme doit afficher la taille de la plus petite région avec exactement une décimale.
Deux propriétés rendent le Voronoi unidimensionnel élégant :
- Chaque village intérieur possède l’intervalle allant de son point médian gauche à son point médian droit.
- Les deux villages aux extrémités possèdent des rayons semi-infinis, donc leurs régions sont toujours infinies et ne sont jamais la réponse.
Pourquoi une approche naïve échoue-t-elle sur le problème des villages de Voronoi ?
Une approche naïve du problème des villages de Voronoi — allouer un emplacement de tableau par coordonnée entière — échoue immédiatement car la plage de coordonnées s’étend sur deux milliards de positions, ce qui dépasse les limites de mémoire typiques. Lorsqu’un problème autorise des coordonnées jusqu’à ±10⁹, allouer un tableau de cette taille générera une erreur limite de mémoire dépassée avant même que votre logique ne s’exécute.
La solution est la compression des coordonnées : stockez uniquement les valeurs que vous avez réellement données. Pour cinq villages, vous avez besoin d’un tableau de longueur cinq, pas de deux milliards. Cela maintient la mémoire à O(N) indépendamment de la dispersion des coordonnées. C’est le même principe qui rend une structure de données de pile puissante — vous ne travaillez qu’avec les données devant vous, pas avec un espace vide que vous ne toucherez jamais.
Comment le tri transforme-t-il le problème des villages de Voronoi ?
Trier les coordonnées d’entrée est l’étape la plus importante du problème des villages de Voronoi car cela transforme une liste chaotique de positions en une séquence ordonnée où chaque village est garanti d’être adjacent à ses véritables voisins géométriques. Sans tri, une boucle sur le tableau comparerait des villages non adjacents et produirait des points médians absurdes.
Appliqué à l’exemple :
- Données brutes : 16, 0, 10, 4, 15
- Après tri : 0, 4, 10, 15, 16
Maintenant, le village 4 se trouve entre 0 et 10, exactement où il doit être sur la droite numérique. Un seul passage de l’index 1 à l’index N−2 (en sautant les deux extrémités) est tout ce dont vous avez besoin. Le tri coûte O(N log N) ; le passage linéaire suivant coûte O(N). Le tri domine, donc la complexité globale est O(N log N).
Quelle est la formule optimisée pour la taille de la région de chaque village ?
Pour tout village intérieur dans le tableau trié, la taille de sa région de Voronoi est égale à la moitié de la distance entre son voisin de droite et son voisin de gauche, exprimée comme : taille = (droite − gauche) / 2. Cette formule unique remplace le calcul en deux étapes pour trouver chaque point médian séparément puis les soustraire.
Voici pourquoi la simplification fonctionne. L’approche naïve calcule :
- Point médian gauche : (actuel + gauche) / 2
- Point médian droit : (droite + actuel) / 2
- Taille de la région : point médian droit − point médian gauche
Développez cette dernière étape algébriquement :
(droite + actuel) / 2 − (actuel + gauche) / 2
= (droite + actuel − actuel − gauche) / 2
= (droite − gauche) / 2
La coordonnée du village s’annule parfaitement. La formule passe directement du voisin de gauche au voisin de droite, sautant complètement la valeur intermédiaire. Cela réduit le nombre d’additions et de divisions dans votre boucle — une petite mais satisfaisante victoire.
Comment appliquez-vous la formule aux coordonnées d’exemple ?
Appliquer la formule à chaque village intérieur dans le tableau trié 0, 4, 10, 15, 16 donne trois tailles de région, et la plus petite est votre réponse. Passer en revue chaque calcul rend le modèle concret.
| Village (actuel) | Voisin de gauche | Voisin de droite | Calcul | Taille de la région |
|---|---|---|---|---|
| 4 | 0 | 10 | (10 − 0) / 2 | 5.0 |
| 10 | 4 | 15 | (15 − 4) / 2 | 5.5 |
| 15 | 10 | 16 | (16 − 10) / 2 | 3.0 |
Minimum courant après chaque étape : 5.0, toujours 5.0, puis 3.0. La réponse est 3.0.
Remarquez que le village 15 est très proche de son voisin de droite 16 (écart de seulement 1) mais loin de son voisin de gauche 10 (écart de 6). La paire serrée à droite comprime la région à 3.0, faisant de 15 le goulet d’étranglement.
Pourquoi le formatage de la sortie est-il important dans le problème des villages de Voronoi ?
Même une réponse mathématiquement correcte sera marquée comme incorrecte en programmation compétitive si elle n’est pas formatée exactement comme le problème le spécifie, et le problème des villages de Voronoi exige généralement exactement une décimale — donc le résultat entier 3 doit être imprimé comme 3.0, pas 3 ou 3.00. Les juges compétitifs utilisent une comparaison de chaînes automatisée ; un point décimal manquant échoue chaque cas de test.
En Python, utilisez print(f"{answer:.1f}"). En C++, utilisez cout << fixed << setprecision(1) << answer;. Ce n’est pas de la pédanterie — c’est une compétence. D’après notre expérience d’enseignement de la programmation compétitive à Intellia Academy, les erreurs de formatage représentent une part surprenante des verdicts de mauvaise réponse évitables sur des solutions par ailleurs parfaites.
La discipline de formatage s’applique bien au-delà de ce problème. Si vous développez des compétences plus larges en raisonnement algorithmique, le concours de pensée computationnelle Bebras est un excellent endroit pour affiner votre attention aux contraintes de sortie précises.
Quelles sont les connexions avec des concepts mathématiques et informatiques plus larges ?
Le problème des villages de Voronoi se situe à l’intersection de la géométrie computationnelle, des algorithmes de tri et de la simplification algébrique — des compétences qui apparaissent dans de nombreuses compétitions académiques. Comprendre cela en profondeur est lié à plusieurs autres idées qui valent la peine d’être explorées.
Compression des coordonnées est une technique utilisée chaque fois que les contraintes du problème donnent de grandes plages de coordonnées mais de petites tailles d’entrée. Elle se retrouve dans les problèmes de requêtes de plage, les algorithmes de balayage et les problèmes de grille en 2D.
Annulation algébrique — l’étape où la coordonnée du village actuel a disparu — est un exemple de simplification d’une expression avant de la coder. Cette habitude évite les bugs et accélère les boucles. Elle fait écho à la logique des preuves mathématiques utilisant des conditions nécessaires vs suffisantes, où le fait de supprimer une structure redondante révèle un argument plus clair.
L’infini comme sentinelle est l’idée que les régions aux extrémités s’étendent à jamais, les rendant automatiquement inéligibles comme minimum. C’est un cas particulier d’utilisation des connaissances du domaine pour élaguer un espace de recherche — une technique centrale aux algorithmes de branchement et de bornage et à de nombreux algorithmes gloutons.
La dominance du tri O(N log N) est un modèle qui se répète à travers les problèmes : lorsqu’un passage linéaire suit un tri, le tri fixe toujours le plafond de complexité globale. Reconnaître cela vous permet de faire rapidement des affirmations sur la complexité temporelle dans les rédactions de compétition.
Si vous appréciez les problèmes qui trouvent une structure cachée dans de grands ensembles de données, vous apprécierez également comment la théorie de Ramsey garantit que l’ordre émerge toujours du chaos apparent — un cousin philosophique de l’idée de Voronoi selon laquelle la structure découle des relations de proximité.
Pour les étudiants visant un succès olympique plus large, le catalogue complet de cours d’Intellia Academy couvre la géométrie computationnelle, les algorithmes et la stratégie de concours à travers les disciplines. Vous pouvez également explorer nos programmes olympiques pour des parcours structurés allant de débutant à prêt pour la compétition.
Résumé de la solution complète pour le problème des villages de Voronoi
Voici l’algorithme complet en langage clair, prêt à être traduit dans n’importe quelle langue :
- Lire les coordonnées des N villages dans un tableau.
- Trier le tableau par ordre croissant — O(N log N).
- Parcourir de l’index 1 à N−2 (sauter le premier et le dernier).
- Calculer
taille = (arr[i+1] − arr[i−1]) / 2.0. - Suivre le minimum courant parmi toutes les tailles calculées.
- Imprimer le minimum avec exactement une décimale.
Pour l’entrée d’exemple (16, 0, 10, 4, 15), la sortie correcte est 3.0.
Un cas particulier à considérer : si N est égal à 2, il n’y a pas de villages intérieurs. Les deux villages sont des extrémités. Selon la garantie du problème, vous devrez peut-être gérer cela séparément — vérifiez soigneusement les contraintes avant de soumettre.
Le jeu de problèmes CSES contient de nombreux problèmes de géométrie unidimensionnelle et de tri qui construisent les mêmes intuitions. Les résoudre systématiquement est l’un des meilleurs moyens d’intérioriser le modèle.
Questions fréquentes sur le problème des villages de Voronoi
Pourquoi les deux villages aux extrémités sont-ils toujours sautés ?
Les villages le plus à gauche et le plus à droite après le tri n’ont pas de voisin d’un côté, donc leur région de Voronoi s’étend à l’infini négatif ou positif. Une région infinie ne peut jamais être la plus petite, donc les sauter est toujours sûr. Essayer de calculer un point médian pour un voisin manquant provoquerait également une erreur de dépassement de tableau.
La formule fonctionne-t-elle si deux villages partagent la même coordonnée ?
Si deux villages partagent une coordonnée, après le tri, ils sont adjacents avec un écart de zéro. La formule donne (suivant − précédent) / 2 où l’écart entre la paire dupliquée est 0, ce qui donne une taille de région de 0.0. Que cela soit valide dépend des contraintes d’entrée du problème ; la plupart des versions garantissent des coordonnées distinctes, donc vérifiez avant de supposer.
Quel langage de programmation est le meilleur pour ce problème ?
Tout langage avec un tri intégré fonctionne. Le sorted() de Python et l’impression formatée le rendent le plus rapide à écrire. C++ est préférable lorsque des délais serrés s’appliquent car son std::sort a des facteurs constants plus bas. Java fonctionne bien avec Arrays.sort(). L’algorithme lui-même est indépendant du langage — la logique est identique dans les trois.
Sources
- La compression des coordonnées ne stocke que les positions de villages données, évitant le crash mémoire causé par l'allocation d'un tableau sur une plage de deux milliards d'entiers.
- Trier les coordonnées par ordre croissant est obligatoire avant tout calcul de distance ; cela garantit que chaque village est adjacent à ses véritables voisins géométriques dans le tableau.
- La formule clé se simplifie en (voisin de droite − voisin de gauche) / 2 car la coordonnée du village actuel s'annule algébriquement, supprimant une étape arithmétique redondante dans la boucle.
- Les deux villages aux extrémités après tri possèdent toujours des régions infinies et ne sont jamais le minimum, donc ils peuvent être sautés en toute sécurité sans aucune comparaison.
- La sortie doit être imprimée avec exactement une décimale (par exemple 3.0, pas 3) car les juges compétitifs utilisent une correspondance de chaînes exacte et un point décimal manquant échoue chaque cas de test.
Transcription complete de la video
Regardez une carte des tours de téléphonie mobile. Chaque maison se connecte à la tour qui est physiquement la plus proche. Lorsque ces zones de couverture physiques se chevauchent, elles créent des limites mathématiques rigides, appelées diagramme de Voronoi. Aujourd'hui, nous allons résoudre le classique problème de programmation des villages de Voronoi en prenant cette structure géométrique exacte et en la plaçant sur une route horizontale droite unidimensionnelle.
Le problème nous donne une route où cinq villages sont situés à des coordonnées spécifiques : 16, 0, 10, 4 et 15. Notre objectif est de trouver la plus petite taille de voisinage parmi eux. L'énoncé précise que ces coordonnées peuvent se situer n'importe où entre moins un milliard et plus un milliard. Si vous essayez de cartographier cela en créant un tableau avec 2 milliards de cases vides, votre programme va planter instantanément avec une erreur de dépassement de mémoire. Nous n'avons besoin de stocker que les cinq coordonnées spécifiques fournies. En ignorant l'espace vide sur la route, nous gardons notre empreinte mémoire petite et notre logique concentrée.
En regardant ce diagramme, remarquez les villages à l'extrême gauche et à l'extrême droite. Il n'y a rien qui les bloque à l'extérieur. Leurs quartiers de couverture s'étendent entièrement à l'infini. Puisque notre objectif est de trouver le plus petit voisinage absolu, un territoire infini ne sera jamais la bonne réponse. Nous pouvons écarter en toute sécurité les bords extérieurs et concentrer nos calculs uniquement sur les villages intérieurs.
Nos données brutes arrivent dans le désordre. Une boucle exécutée maintenant calcule les distances entre des non-voisins. Mais chaque fois que vous traitez des données spatiales unidimensionnelles, votre première étape est le tri. Les villages se rangent dans l'ordre croissant : 0, 4, 10, 15, 16. Maintenant parfaitement coincés entre des voisins réels. Avec une fonction de tri standard, la recherche spatiale devient un parcours linéaire à travers un tableau.
Calculons la taille pour le village 4. L'approche standard trouve les points médians gauche et droit et les soustrait, ce qui donne 5.0. Maintenant, regardez ces trois formules. Pouvez-vous les combiner algébriquement pour éliminer la variable redondante ? En combinant les fractions, nous fusionnons les calculs en une seule équation. Les versions positive et négative de la coordonnée du village actuel s'annulent parfaitement. Le processus se réduit à une formule élégante : le voisin de droite moins le voisin de gauche divisé par 2.
En retirant le village actuel de son propre calcul, nous réduisons le travail computationnel nécessaire à l'intérieur de votre boucle. En appliquant notre formule optimisée au village 10, la logique passe directement de 4 à 15. 11 divisé par 2 donne 5.5. Puisque 5.5 est supérieur à notre minimum actuel de 5.0, nous passons au village suivant. Nous testons notre dernier village à 15. Le voisin de droite 16 moins le voisin de gauche 10 donne 6. Divisé par 2, nous obtenons 3.0. Puisque 3.0 est inférieur à notre précédent 5.0, le tableau de scores se met à jour avec notre nouveau minimum.
Formaliser l'efficacité. Parcourir le tableau prend un temps O(N), mais l'étape de tri initiale prend un temps O(N log N). Comme le tri est l'opération la plus intensive, notre complexité temporelle globale est O(N log N).
Les juges de compétition sont stricts en ce qui concerne le format de sortie. Même si vos calculs aboutissent à un entier parfait, comme 3, la solution échouera si elle ne fournit pas exactement une décimale, 3.0. Résoudre ces défis repose sur l'intuition spatiale, la simplification algébrique et le respect strict du formatage technique.