Calcul de l'enveloppe convexe d'un nuage de points : algorithme du paquet cadeau et algorithme de balayage (Graham-Andrew)
Afficher ou masquer la section
Le sujet, commun aux filières MP et PC, porte sur le calcul de l'enveloppe convexe d'un nuage de points dans le plan, un problème classique de géométrie algorithmique. Après des questions préliminaires sur l'ordre des points, il fait étudier deux algorithmes : le « paquet cadeau », de complexité O(n·m), puis un algorithme de balayage utilisant des piles, de complexité O(n·log n).
1Partie I : PréliminairesRecherche du point le plus bas du nuage et écriture du test d'orientation de trois points.
2Partie II : Algorithme du paquet cadeauConstruction d'un ordre total sur les points, puis programmation de l'algorithme du paquet cadeau et justification de sa complexité en O(n·m).
3Partie III : Algorithme de balayageMise à jour des enveloppes supérieure et inférieure à l'aide de piles, puis assemblage et analyse de la complexité amortie en O(n·log n) de l'algorithme de Graham-Andrew.
Difficile. Le rapport qualifie la question sur la mise à jour de l'enveloppe supérieure de 'clairement difficile', et la question finale d'analyse de complexité amortie a obtenu 0 point pour 84,7% des candidats de la filière PC.
Ce qu'a observé le jury
6 erreurs relevées
Analyse de complexité amortie non maîtrisée · Mise à jour de l'enveloppe supérieure avec une pile · Mauvais choix d'algorithme de tri
Afficher ou masquer la section
L'épreuve, corrigée séparément pour les filières MP (540 candidats admissibles, moyenne 14,23, écart-type 2,79) et PC (551 candidats, moyenne 10,90, écart-type 2,86), porte sur un problème classique de géométrie algorithmique. Le jury insiste sur l'importance de la lisibilité et de la rigueur du code, en plus de sa correction, et relève de nombreuses difficultés sur les questions d'analyse de complexité en fin d'épreuve.
Les erreurs les plus sanctionnées
1
Analyse de complexité amortie non maîtriséeQ13
De nombreux candidats restent bloqués sur la question finale, ne comprenant pas comment conclure à une complexité en n log n après avoir vu une complexité apparente en n².
« candidats ont été bloqués à ce niveau, ne comprenant pas comm ent on pouvait finalement conclure en une complexité en n log n. »
2
Mise à jour de l'enveloppe supérieure avec une pileQ10
Cette question, jugée clairement difficile par le jury, a donné lieu à des réponses très inégales, de quelques lignes à plusieurs dizaines.
« Cette question est clairement difficile, les propositions vo nt de 5 lignes à plusieurs »
3
Mauvais choix d'algorithme de triQ9
Des candidats proposent le tri à bulles, qui n'est pas en O(n log n), ou présentent le tri rapide comme ayant une complexité garantie en n log n alors qu'il est quadratique dans le pire cas.
4
Preuve de transitivité mal maîtriséeQ4
De nombreux candidats se perdent dans une preuve calculatoire de la transitivité et multiplient une inégalité par un scalaire sans tenir compte de son signe.
5
Non-respect de l'abstraction des pilesQ10, Q11
Le sujet imposait d'utiliser uniquement les opérations fournies sur les piles plutôt que de manipuler directement les listes sous-jacentes ; cette contrainte a été mal comprise et peu respectée.
6
Code juste mais illisible
Certaines solutions justes restent totalement tordues, avec un code très difficile à lire et à comprendre.
Ce qui a été bien réussi
La question sur le point le plus bas du nuage (Q1) a été plutôt bien traitée en moyenne, sans vraie difficulté.
La question de cours sur un algorithme de tri en O(n·log n) (Q9) a été très bien réussie, avec la totalité des points pour 90,6% des candidats MP.
La question symétrique sur l'enveloppe inférieure (Q11) a été bien traitée par 74,5% des candidats MP.
Conseils du jury
Soigner la lisibilité et la structuration du code : indentation des boucles et tests, passages à la ligne.
Réutiliser les fonctions écrites aux questions précédentes plutôt que tout refaire.
Éviter d'appeler plusieurs fois la même fonction dans une boucle ; stocker le résultat en mémoire.
Vérifier systématiquement que les indices utilisés ne dépassent pas la taille du tableau.
Respecter les contraintes de l'énoncé, notamment l'usage imposé de structures de données comme les piles.
Justifier soigneusement une analyse de complexité, y compris lorsqu'elle nécessite un raisonnement amorti.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
ÉCOLE POLYTECHNIQUE - ÉCOLES NORMALES SUPÉRIEURES
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES
COMPOSITION D'INFORMATIQUE - B - (XECLR)
(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
Enveloppes convexes dans le plan
Ce sujet a pour objectif de calculer des enveloppes convexes de nuages de points dans le plan affine, un grand classique en géométrie algorithmique. On rappelle qu'un ensemble C ⊆ ℝ^2 est convexe si et seulement si pour toute paire de points p, q ∈ C, le segment de droite [p, q] est inclus dans C. L'enveloppe convexe d'un ensemble P ⊆ ℝ^2, notée Conv(P), est le plus petit convexe contenant P. Dans le cas où P est un ensemble fini (appelé nuage de points), le bord de Conv(P) est un polygône convexe dont les sommets appartiennent à P, comme illustré dans la figure 1.
Figure 1 - Un nuage de points, numérotés de 0 à 11, et le bord de son enveloppe convexe.
Le calcul de l'enveloppe convexe d'un nuage de points est un problème fondamental en informatique, qui trouve des applications dans de nombreux domaines comme :
la robotique, par exemple pour l'accélération de la détection de collisions dans le cadre de la planification de trajectoire,
le traitement d'images et la vision, par exemple pour la détection d'objets convexes (comme des plaques minéralogiques de voiture) dans des scènes 2 d ,
l'informatique graphique, par exemple pour l'accélération du rendu de scènes 3d par lancer de rayons,
la théorie des jeux, par exemple pour déterminer l'existence d'équilibres de Nash,
la vérification formelle, par exemple pour déterminer si une variable risque de dépasser sa capacité de stockage ou d'atteindre un ensemble de valeurs interdites lors de l'exécution d'une boucle dans un programme,
et bien d'autres encore.
Dans ce sujet nous allons écrire deux algorithmes de calcul du bord de l'enveloppe convexe d'un nuage de points P dans le plan affine. Le premier, dit algorithme du paquet cadeau, consiste à envelopper le nuage de points P progressivement en faisant pivoter une droite tout autour. Le deuxième, dit de balayage, consiste à balayer le plan horizontalement avec une droite verticale, tout en maintenant au fur et à mesure l'enveloppe convexe de la partie du nuage située à gauche de cette droite verticale. Les deux algorithmes sont illustrés respectivement dans les figures 3 et 4 .
Le temps d'exécution du premier algorithme est majoré par une constante fois nm, celui du deuxième par une constante fois nlogn, où n désigne le nombre total de points de P et m le nombre de points de P appartenant au bord de Conv(P). Rappelons que le temps d'exécution d'un programme A (fonction ou procédure) est le nombre d'opérations élémentaires (comparaisons, additions, soustractions, multiplications, divisions, affectations, etc.) nécessaires à l'exécution de A. Sauf mention contraire dans l'énoncé du sujet, le candidat n'aura pas à justifier des temps de calcul de ses programmes. Toutefois, il devra veiller à ce que ces derniers ne dépassent pas les bornes prescrites.
Dans toute la suite on supposera que le nuage de points P est de taille n ≥ 3 et en position générale, c'est-à-dire qu'il ne contient pas 3 points distincts alignés.
Ces hypothèses vont permettre de simplifier les calculs en ignorant les cas pathologiques, comme par exemple la présence de 3 points alignés sur le bord de l'enveloppe convexe. Nos programmes prendront en entrée un nuage de points P dont les coordonnées sont stockées dans un tableau tab à 2 dimensions, comme dans l'exemple ci-dessous qui contient les coordonnées du nuage de points de la figure 1 :
i∖j
0
1
2
3
4
5
6
7
8
9
10
11
0
0
1
1
4
4
5
5
7
7
8
11
13
1
0
4
8
1
4
9
6
-1
2
5
6
1
Précisons que les coordonnées, supposées entières, sont données dans une base orthonormée du plan, orientée dans le sens direct. La première ligne du tableau contient les abscisses, tandis que la deuxième contient les ordonnées. Ainsi, la colonne d'indice j contient les deux coordonnées du point d'indice j. Ce dernier sera nommé p_j dans la suite.
Partie I. Préliminaires
Question 1 Écrire une fonction plusBas (tab, n) qui prend en paramètre le tableau tab de taille 2 × n et qui renvoie l'indice j du point le plus bas (c'est-à-dire de plus petite ordonnée) parmi les points du nuage P. En cas d'égalité, votre fonction devra renvoyer l'indice du point de plus petite abscisse parmi les points les plus bas.
Sur le tableau exemple précédent, le résultat de la fonction doit être l'indice 7.
Dans la suite nous aurons besoin d'effectuer un seul type de test géométrique : celui de l'orientation.
Définition 1 Étant donnés trois points p_i, p_j, p_k du nuage P, distincts ou non, le test d'orientation renvoie +1 si la séquence ( p_i, p_j, p_k ) est orientée positivement, -1 si elle est orientée négativement, et 0 si les trois points sont alignés (c'est-à-dire si deux au moins sont égaux, d'après l'hypothèse de position générale).
Pour déterminer l'orientation de ( p_i, p_j, p_k ), il suffit de calculer l'aire signée du triangle, comme illustré sur la figure 2 . Cette aire est la moitié du déterminant de la matrice 2 × 2 formée par les coordonnées des vecteurs p_i p_j^(→−) et p_i p_k^(→−).
Figure 2 - Test d'orientation sur la séquence ( p_i, p_j, p_k ) : positif à gauche, nul au centre, négatif à droite.
Question 2 Sur le tableau exemple précédent, donner le résultat du test d'orientation pour les choix d'indices suivants : − i = 0, j = 3, k = 4, − i = 8, j = 9, k = 10.
Question 3 Écrire une fonction orient (tab, i, j, k) qui prend en paramètres le tableau tab et trois indices de colonnes, potentiellement égaux, et qui renvoie le résultat ( − 1, 0 ou +1 ) du test d'orientation sur la séquence ( p_i, p_j, p_k ) de points de P.
Partie II. Algorithme du paquet cadeau
Cet algorithme a été proposé par R. Jarvis en 1973. Il consiste à envelopper peu à peu le nuage de points P dans une sorte de paquet cadeau, qui à la fin du processus est exactement le bord de Conv(P). On commence par insérer le point de plus petite ordonnée (celui d'indice 7 dans l'exemple de la figure 1) dans le paquet cadeau, puis à chaque étape de la procédure on sélectionne le prochain point du nuage P à insérer.
La procédure de sélection fonctionne comme suit. Soit p_i le dernier point inséré dans le paquet cadeau à cet instant. Par exemple, i = 10 dans l'exemple de la figure 3 . Considérons la
Figure 3 - Mise à jour du paquet cadeau après insertion du point p_(10).
relation binaire ⪯ définie sur l'ensemble P∖{p_i} par :
p_j⪯p_k ⟺ orient (tab, i, j, k) ≤ 0.
Question 4 Justifier brièvement le fait que ⪯ est une relation d'ordre total sur l'ensemble P∖{p_i}, c'est-à-dire :
(réflexivité) pour tout j ≠ i, p_j⪯p_j,
(antisymétrie) pour tous j, k ≠ i, p_j⪯p_k et p_k⪯p_j implique j = k,
(transitivité) pour tous j, k, l ≠ i, p_j⪯p_k et p_k⪯p_l implique p_j⪯p_l,
(totalité) pour tous j, k ≠ i, p_j⪯p_k ou p_k⪯p_j.
Ainsi, le prochain point à insérer (le point d'indice 5 dans la figure 3) est l'élément maximum pour la relation d'ordre ⪯. Il peut se calculer en temps linéaire (c'est-à-dire majoré par une constante fois n ) par une simple itération sur les points de P∖{p_i}.
Question 5 Décrire une réalisation en Python de la procédure. Elle prendra la forme d'une fonction prochainPoint (tab, n, i), qui prend en paramètre le tableau tab de taille 2 × n ainsi que l'indice i du point inséré en dernier dans le paquet cadeau, et qui renvoie l'indice du prochain point à insérer. Le temps d'exécution de votre fonction doit être majoré par une constante fois n, pour tous n et i. La constante doit être indépendante de n et i, et on ne demande pas de la préciser.
Question 6 Décrire à la main le déroulement de la procédure prochainPoint sur l'exemple de la figure 3. Plus précisément, indiquer la séquence des points de P∖{p_(10)} considérés et la valeur de l'indice du maximum à chaque itération.
On peut maintenant combiner la fonction prochainPoint avec la fonction plusBas de la question 1 pour calculer le bord de l'enveloppe convexe de P. On commence par insérer le point p_i d'ordonnée la plus basse, puis on itère le processus de mise à jour du paquet cadeau jusqu'à ce que le prochain point à insérer soit de nouveau p_i. À ce moment-là on renvoie le paquet cadeau comme résultat sans insérer p_i une seconde fois.
Un détail technique : comme la taille du paquet cadeau augmente peu à peu lors du processus, et qu'à la fin elle peut être petite par rapport au nombre n de points de P, nous stockerons les
indices des points du paquet cadeau dans une liste. Par exemple, sur le nuage de la figure 1, le résultat sera la liste [7, 11, 10, 5, 2, 0].
Question 7 Écrire une fonction convJarvis (tab, n) qui prend en paramètre le tableau tab de taille 2 × n représentant le nuage P, et qui renvoie une liste contenant les indices des sommets du bord de l'enveloppe convexe de P, sans doublon. Le temps d'exécution de votre fonction doit être majoré par une constante fois nm, où m est le nombre de points de P situés sur le bord de Conv(P).
Question 8 Justifier brièvement le temps d'exécution de l'algorithme du paquet cadeau.
Intermède : piles d'entiers
Dans la suite nous aurons besoin d'utiliser des piles d'entiers, dont on rappelle la définition ci-dessous :
Définition 2 Une pile d'entiers est une structure de données permettant de stocker des entiers et d'effectuer les opérations suivantes en temps constant (indépendant de la taille de la pile) :
créer une nouvelle pile vide,
déterminer si la pile est vide,
insérer un entier au sommet de la pile,
déterminer la valeur de l'entier au sommet de la pile,
retirer l'entier au sommet de la pile.
Nous supposerons fournies les fonctions suivantes, qui réalisent les opérations ci-dessus et s'executent chacune en temps constant :
newStack(), qui ne prend pas d'argument et renvoie une pile vide,
isEmpty( s ), qui prend une pile s en argument et renvoie True ou False suivant que s est vide ou non,
push (i, s), qui prend un entier i et une pile s en argument, insère i au sommet de s (c'est-à-dire à la fin de la liste), et ne renvoie rien,
top(s), qui prend une pile s (supposée non vide) en argument et renvoie la valeur de l'entier au sommet de s (c'est-à-dire à la fin de la liste),
pop (s), qui prend une pile s (supposée non vide) en argument, supprime l'entier au sommet de s (c'est-à-dire à la fin de la liste) et renvoie sa valeur.
Dans la suite il est demandé aux candidats de manipuler les piles uniquement au travers de ces fonctions, sans aucune hypothèse sur la représentation effective des piles en mémoire.
Partie III. Algorithme de balayage
Cet algorithme a été proposé par R. Graham en 1972. Nous allons écrire la variante (plus simple) proposée par A. Andrew quelques années plus tard.
La première étape consiste à trier les n points du nuage P par ordre croissant d'abscisse, en conservant tous les points de même abscisse dans un ordre arbitraire.
Question 9 Parmi les algorithmes de tri que vous connaissez, mentionnez-en un qui a un temps d'exécution majoré par une constante fois nlogn sur les entrées de taille n.
À partir de maintenant, on supposera que les points fournis en entrée sont triés par abscisse croissante, comme c'est le cas dans l'exemple du tableau tab donné au début du sujet.
L'idée de l'algorithme est de balayer le nuage de points horizontalement de gauche à droite par une droite verticale, tout en mettant à jour l'enveloppe convexe des points de P situés à gauche de cette droite, comme illustré dans la figure 4.
Figure 4 - Diverses étapes dans la procédure de balayage. La droite de balayage est en tirets.
Plus précisément, l'algorithme visite chaque point de P une fois, par ordre croissant d'abscisse (donc par ordre croissant d'indice de colonne dans le tableau tab car celui-ci est trié). À chaque nouveau point p_i visité, il met à jour le bord de l'enveloppe convexe du sous-nuage {p_0, ⋯, p_i} situé à gauche de p_i. On remarque que les points p_0 et p_i sont sur ce bord, et on appelle enveloppe supérieure la partie du bord de Conv{p_0, ⋯, p_i} située au-dessus de la droite passant par p_0 et p_i ( p_0 et p_i compris), et enveloppe inférieure la partie du bord de Conv{p_0, ⋯, p_i} située au-dessous ( p_0 et p_i compris). Le bord de Conv{p_0, ⋯, p_i} est donc constitué de l'union de ces deux enveloppes, après suppression des doublons de p_0 et p_i.
Par exemple, dans le cas du nuage P de la figure 4 gauche, le sous-nuage {p_0, p_1, p_2, p_3, p_4} a pour enveloppe supérieure la séquence (p_0, p_2, p_4) et pour enveloppe inférieure la séquence (p_0, p_3, p_4), le bord de son enveloppe convexe étant donné par la séquence ( p_0, p_3, p_4, p_2 ).
Informatiquement, les indices des sommets des enveloppes inférieure et supérieure seront stockés dans deux piles d'entiers séparées, ei (pour enveloppe inférieure) et es (pour enveloppe supérieure).
La mise à jour de l'enveloppe supérieure est illustrée dans la figure 5 : tant que le point visité ( p_9 dans ce cas) et les deux points dont les indices sont situés au sommet de la pile es (dans l'ordre: p_8 et p_5 ) forme une séquence ( p_9, p_8, p_5 ) d'orientation négative (voir la définition 1 pour rappel de l'orientation), on dépile l'indice situé au sommet de es ( 8 dans ce cas). On poursuit ce processus d'élimination jusqu'à ce que l'orientation devienne positive ou qu'il ne reste plus qu'un seul indice dans la pile. L'indice du point visité ( p_9 dans ce cas) est alors inséré au sommet de es. La mise à jour de l'enveloppe inférieure s'opère de manière symétrique.
Figure 5 - Mise à jour de l'enveloppe supérieure lors de la visite du point p_9.
Question 10 Écrire une fonction majES( tab, es, i ) qui prend en paramètre le tableau tab ainsi que la pile es et l'indice i du point à visiter, et qui met à jour l'enveloppe supérieure du sousnuage. Le temps d'exécution de votre fonction doit être majoré par une constante fois i.
Question 11 Écrire une fonction majEI (tab, ei, i) qui effectue la mise à jour de l'enveloppe inférieure, avec le même temps d'exécution.
Question 12 Écrire maintenant une fonction convGraham (tab, n) qui prend en paramètre le tableau tab de taille 2 × n représentant le nuage P, et qui effectue le balayage des points de P comme décrit précédemment. On supposera les colonnes du tableau tab déjà triées par ordre croissant d'abscisse. La fonction doit renvoyer une pile s contenant les indices des sommets du bord de Conv(P) triés dans l'ordre positif d'orientation, à commencer par le point p_0.
Par exemple, sur le nuage de la figure 1, le résultat de la fonction convGraham doit être la pile s contenant la suite d'incides 0, 7, 11, 10, 5, 2 dans cet ordre, l'indice 0 se trouvant au fond de la pile s et l'indice 2 au sommet de s.
Question 13 Analyser brièvement le temps d'exécution de l'algorithme de balayage décrit précédemment, en supposant une fois encore que les points du nuage fourni en entrée sont déjà triés par abscisse croissante. En déduire que le temps d'exécution total de l'algorithme de Graham-Andrew est bien majoré par une constante fois nlogn.
Questions fréquentes
4 questions
Sur quels chapitres porte l'épreuve d'informatique commune X-ENS MP-PC 2015 ?
Afficher ou masquer la section
Sur quels chapitres porte l'épreuve d'informatique commune X-ENS MP-PC 2015 ?
+
L'épreuve porte sur le calcul de l'enveloppe convexe d'un nuage de points, avec l'algorithme du paquet cadeau puis un algorithme de balayage utilisant des piles, ce qui mobilise l'algorithmique, l'analyse de complexité et la programmation Python.
Quelles erreurs le jury a-t-il le plus relevées sur cette épreuve d'informatique X-ENS 2015 ?
+
Le jury relève des difficultés sur l'analyse de complexité amortie de la dernière question, un mauvais choix d'algorithme de tri, une preuve de transitivité mal maîtrisée et un non-respect de la contrainte d'utiliser les piles comme structure abstraite.
L'épreuve d'informatique commune X-ENS 2015 est-elle plus difficile en MP ou en PC ?
+
D'après les statistiques du rapport, la moyenne est plus élevée en MP (14,23/20) qu'en PC (10,90/20), pour un sujet pourtant commun aux deux filières.
Quelle est la dernière question la plus difficile du sujet X-ENS informatique commune 2015 ?
+
La question 13, qui demandait de justifier la complexité en n log n de l'algorithme de balayage par un argument amorti, a obtenu 0 point pour 84,7% des candidats de la filière PC.
Pas de description pour le moment
Commentaires• X ENS Informatique Commune MP PC 2015
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même chapitre : Programmation en Python (+1)CCINP Informatique Commune PC PSI 2023CCINP · 2023Corrigé
Même année, CentraleCentrale Option Informatique MP 2015Centrale · 2015Corrigé
