ECOLE POLYTECHNIQUE ECOLES NORMALES SUPERIEURES ECOLE SUPERIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES CONCOURS D'ADMISSION 2015 FILIERE MP HORS SPECIALITE INFO FILIERE PC COMPOSITION D'INFORMATIQUE B (XECLR) (Duree : 2 heures) L'utilisation des calculatrices n'est pas autorisee pour cette epreuve. Le langage de programmation choisi par le candidat doit etre specifie en tete 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 geometrie algorithmique. On rappelle qu'un ensemble C R2 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 R2 , notee Conv(P ), est le plus petit convexe contenant P . Dans le cas ou P est un ensemble fini (appele nuage de points), le bord de Conv(P ) est un polygone convexe dont les sommets appartiennent a P , comme illustre dans la figure 1. 5 2 10 6 1 9 4 8 11 3 0 7 Figure 1 Un nuage de points, numerotes de 0 a 11, et le bord de son enveloppe convexe. Le calcul de l'enveloppe convexe d'un nuage de points est un probleme fondamental en informatique, qui trouve des applications dans de nombreux domaines comme : la robotique, par exemple pour l'acceleration de la detection de collisions dans le cadre de la planification de trajectoire, 1 le traitement d'images et la vision, par exemple pour la detection d'objets convexes (comme des plaques mineralogiques de voiture) dans des scenes 2d, l'informatique graphique, par exemple pour l'acceleration du rendu de scenes 3d par lancer de rayons, la theorie des jeux, par exemple pour determiner l'existence d'equilibres de Nash, la verification formelle, par exemple pour determiner si une variable risque de depasser sa capacite de stockage ou d'atteindre un ensemble de valeurs interdites lors de l'execution d'une boucle dans un programme, et bien d'autres encore. Dans ce sujet nous allons ecrire 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 a envelopper le nuage de points P progressivement en faisant pivoter une droite tout autour. Le deuxieme, dit de balayage, consiste a balayer le plan horizontalement avec une droite verticale, tout en maintenant au fur et a mesure l'enveloppe convexe de la partie du nuage situee a gauche de cette droite verticale. Les deux algorithmes sont illustres respectivement dans les figures 3 et 4. Le temps d'execution du premier algorithme est majore par une constante fois nm, celui du deuxieme par une constante fois n log n, ou n designe 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'execution d'un programme A (fonction ou procedure) est le nombre d'operations elementaires (comparaisons, additions, soustractions, multiplications, divisions, affectations, etc.) necessaires a l'execution de A. Sauf mention contraire dans l'enonce du sujet, le candidat n'aura pas a justifier des temps de calcul de ses programmes. Toutefois, il devra veiller a ce que ces derniers ne depassent pas les bornes prescrites. Dans toute la suite on supposera que le nuage de points P est de taille n 3 et en position generale, c'est-a-dire qu'il ne contient pas 3 points distincts alignes. Ces hypotheses vont permettre de simplifier les calculs en ignorant les cas pathologiques, comme par exemple la presence de 3 points alignes sur le bord de l'enveloppe convexe. Nos programmes prendront en entree un nuage de points P dont les coordonnees sont stockees dans un tableau tab a 2 dimensions, comme dans l'exemple ci-dessous qui contient les coordonnees du nuage de points de la figure 1 : i\j 0 1 0 0 0 1 1 4 2 1 8 3 4 1 4 4 4 5 5 9 6 5 6 7 7 -1 8 7 2 9 8 5 10 11 6 11 13 1 Precisons que les coordonnees, supposees entieres, sont donnees dans une base orthonormee du plan, orientee dans le sens direct. La premiere ligne du tableau contient les abscisses, tandis que la deuxieme contient les ordonnees. Ainsi, la colonne d'indice j contient les deux coordonnees du point d'indice j. Ce dernier sera nomme pj dans la suite. 2 Partie I. Preliminaires Question 1 Ecrire une fonction plusBas(tab, n) qui prend en parametre le tableau tab de taille 2 × n et qui renvoie l'indice j du point le plus bas (c'est-a-dire de plus petite ordonnee) parmi les points du nuage P . En cas d'egalite, votre fonction devra renvoyer l'indice du point de plus petite abscisse parmi les points les plus bas. Sur le tableau exemple precedent, le resultat de la fonction doit etre l'indice 7. Dans la suite nous aurons besoin d'effectuer un seul type de test geometrique : celui de l'orientation. Definition 1 Etant donnes trois points pi , pj , pk du nuage P , distincts ou non, le test d'orientation renvoie +1 si la sequence (pi , pj , pk ) est orientee positivement, -1 si elle est orientee negativement, et 0 si les trois points sont alignes (c'est-a-dire si deux au moins sont egaux, d'apres l'hypothese de position generale). Pour determiner l'orientation de (pi , pj , pk ), il suffit de calculer l'aire signee du triangle, comme illustre sur la figure 2. Cette aire est la moitie du determinant de la matrice 2 × 2 formee -- par les coordonnees des vecteurs - p- i pj et pi pk . pk pj pj + - pj pi p pk i pi = pk Figure 2 Test d'orientation sur la sequence (pi , pj , pk ) : positif a gauche, nul au centre, negatif a droite. Question 2 Sur le tableau exemple precedent, donner le resultat du test d'orientation pour les choix d'indices suivants : i = 0, j = 3, k = 4, i = 8, j = 9, k = 10. Question 3 Ecrire une fonction orient(tab, i, j, k) qui prend en parametres le tableau tab et trois indices de colonnes, potentiellement egaux, et qui renvoie le resultat (-1, 0 ou +1) du test d'orientation sur la sequence (pi , pj , pk ) de points de P . Partie II. Algorithme du paquet cadeau Cet algorithme a ete propose par R. Jarvis en 1973. Il consiste a envelopper peu a peu le nuage de points P dans une sorte de paquet cadeau, qui a la fin du processus est exactement le bord de Conv(P ). On commence par inserer le point de plus petite ordonnee (celui d'indice 7 dans l'exemple de la figure 1) dans le paquet cadeau, puis a chaque etape de la procedure on selectionne le prochain point du nuage P a inserer. 3 La procedure de selection fonctionne comme suit. Soit pi le dernier point insere dans le paquet cadeau a cet instant. Par exemple, i = 10 dans l'exemple de la figure 3. Considerons la 5 2 10 6 1 9 4 8 11 3 0 7 Figure 3 Mise a jour du paquet cadeau apres insertion du point p10 . relation binaire definie sur l'ensemble P \ {pi } par : p j pk orient(tab, i, j, k) 0. Question 4 Justifier brievement le fait que est une relation d'ordre total sur l'ensemble P \ {pi }, c'est-a-dire : - (reflexivite) pour tout j 6= i, pj pj , - (antisymetrie) pour tous j, k 6= i, pj pk et pk pj implique j = k, - (transitivite) pour tous j, k, l 6= i, pj pk et pk pl implique pj pl , - (totalite) pour tous j, k 6= i, pj pk ou pk pj . Ainsi, le prochain point a inserer (le point d'indice 5 dans la figure 3) est l'element maximum pour la relation d'ordre . Il peut se calculer en temps lineaire (c'est-a-dire majore par une constante fois n) par une simple iteration sur les points de P \ {pi }. Question 5 Decrire une realisation en Python de la procedure. Elle prendra la forme d'une fonction prochainPoint(tab, n, i), qui prend en parametre le tableau tab de taille 2 × n ainsi que l'indice i du point insere en dernier dans le paquet cadeau, et qui renvoie l'indice du prochain point a inserer. Le temps d'execution de votre fonction doit etre majore par une constante fois n, pour tous n et i. La constante doit etre independante de n et i, et on ne demande pas de la preciser. Question 6 Decrire a la main le deroulement de la procedure prochainPoint sur l'exemple de la figure 3. Plus precisement, indiquer la sequence des points de P \ {p10 } consideres et la valeur de l'indice du maximum a chaque iteration. 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 inserer le point pi d'ordonnee la plus basse, puis on itere le processus de mise a jour du paquet cadeau jusqu'a ce que le prochain point a inserer soit de nouveau pi . A ce moment-la on renvoie le paquet cadeau comme resultat sans inserer pi une seconde fois. Un detail technique : comme la taille du paquet cadeau augmente peu a peu lors du processus, et qu'a la fin elle peut etre petite par rapport au nombre n de points de P , nous stockerons les 4 indices des points du paquet cadeau dans une liste. Par exemple, sur le nuage de la figure 1, le resultat sera la liste [7, 11, 10, 5, 2, 0]. Question 7 Ecrire une fonction convJarvis(tab, n) qui prend en parametre le tableau tab de taille 2 × n representant 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'execution de votre fonction doit etre majore par une constante fois nm, ou m est le nombre de points de P situes sur le bord de Conv(P ). Question 8 Justifier brievement le temps d'execution de l'algorithme du paquet cadeau. Intermede : piles d'entiers Dans la suite nous aurons besoin d'utiliser des piles d'entiers, dont on rappelle la definition ci-dessous : Definition 2 Une pile d'entiers est une structure de donnees permettant de stocker des entiers et d'effectuer les operations suivantes en temps constant (independant de la taille de la pile) : creer une nouvelle pile vide, determiner si la pile est vide, inserer un entier au sommet de la pile, determiner 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 realisent les operations 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, insere i au sommet de s (c'esta-dire a la fin de la liste), et ne renvoie rien, top(s), qui prend une pile s (supposee non vide) en argument et renvoie la valeur de l'entier au sommet de s (c'est-a-dire a la fin de la liste), pop(s), qui prend une pile s (supposee non vide) en argument, supprime l'entier au sommet de s (c'est-a-dire a la fin de la liste) et renvoie sa valeur. Dans la suite il est demande aux candidats de manipuler les piles uniquement au travers de ces fonctions, sans aucune hypothese sur la representation effective des piles en memoire. Partie III. Algorithme de balayage Cet algorithme a ete propose par R. Graham en 1972. Nous allons ecrire la variante (plus simple) proposee par A. Andrew quelques annees plus tard. 5 La premiere etape consiste a trier les n points du nuage P par ordre croissant d'abscisse, en conservant tous les points de meme abscisse dans un ordre arbitraire. Question 9 Parmi les algorithmes de tri que vous connaissez, mentionnez-en un qui a un temps d'execution majore par une constante fois n log n sur les entrees de taille n. A partir de maintenant, on supposera que les points fournis en entree sont tries par abscisse croissante, comme c'est le cas dans l'exemple du tableau tab donne au debut du sujet. L'idee de l'algorithme est de balayer le nuage de points horizontalement de gauche a droite par une droite verticale, tout en mettant a jour l'enveloppe convexe des points de P situes a gauche de cette droite, comme illustre dans la figure 4. 5 5 5 2 2 10 6 1 2 4 10 6 9 1 4 11 0 4 8 11 3 0 7 1 9 8 8 3 10 6 9 11 3 0 7 7 Figure 4 Diverses etapes dans la procedure de balayage. La droite de balayage est en tirets. Plus precisement, 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 trie). A chaque nouveau point pi visite, il met a jour le bord de l'enveloppe convexe du sous-nuage {p0 , · · · , pi } situe a gauche de pi . On remarque que les points p0 et pi sont sur ce bord, et on appelle enveloppe superieure la partie du bord de Conv{p0 , · · · , pi } situee au-dessus de la droite passant par p0 et pi (p0 et pi compris), et enveloppe inferieure la partie du bord de Conv{p0 , · · · , pi } situee au-dessous (p0 et pi compris). Le bord de Conv{p0 , · · · , pi } est donc constitue de l'union de ces deux enveloppes, apres suppression des doublons de p0 et pi . Par exemple, dans le cas du nuage P de la figure 4 gauche, le sous-nuage {p0 , p1 , p2 , p3 , p4 } a pour enveloppe superieure la sequence (p0 , p2 , p4 ) et pour enveloppe inferieure la sequence (p0 , p3 , p4 ), le bord de son enveloppe convexe etant donne par la sequence (p0 , p3 , p4 , p2 ). Informatiquement, les indices des sommets des enveloppes inferieure et superieure seront stockes dans deux piles d'entiers separees, ei (pour enveloppe inferieure) et es (pour enveloppe superieure). La mise a jour de l'enveloppe superieure est illustree dans la figure 5 : tant que le point visite (p9 dans ce cas) et les deux points dont les indices sont situes au sommet de la pile es (dans l'ordre : p8 et p5 ) forme une sequence (p9 , p8 , p5 ) d'orientation negative (voir la definition 1 pour rappel de l'orientation), on depile l'indice situe au sommet de es (8 dans ce cas). On poursuit ce processus d'elimination jusqu'a ce que l'orientation devienne positive ou qu'il ne reste plus qu'un seul indice dans la pile. L'indice du point visite (p9 dans ce cas) est alors insere au sommet de es. La mise a jour de l'enveloppe inferieure s'opere de maniere symetrique. 6 5 5 2 2 1 4 + 10 6 5 2 10 6 - 9 1 4 11 0 4 8 11 3 0 7 1 9 8 8 3 10 6 9 11 3 0 7 7 Figure 5 Mise a jour de l'enveloppe superieure lors de la visite du point p9 . Question 10 Ecrire une fonction majES(tab, es, i) qui prend en parametre le tableau tab ainsi que la pile es et l'indice i du point a visiter, et qui met a jour l'enveloppe superieure du sousnuage. Le temps d'execution de votre fonction doit etre majore par une constante fois i. Question 11 Ecrire une fonction majEI(tab, ei, i) qui effectue la mise a jour de l'enveloppe inferieure, avec le meme temps d'execution. Question 12 Ecrire maintenant une fonction convGraham(tab, n) qui prend en parametre le tableau tab de taille 2 × n representant le nuage P , et qui effectue le balayage des points de P comme decrit precedemment. On supposera les colonnes du tableau tab deja triees par ordre croissant d'abscisse. La fonction doit renvoyer une pile s contenant les indices des sommets du bord de Conv(P ) tries dans l'ordre positif d'orientation, a commencer par le point p0 . Par exemple, sur le nuage de la figure 1, le resultat de la fonction convGraham doit etre 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 brievement le temps d'execution de l'algorithme de balayage decrit precedemment, en supposant une fois encore que les points du nuage fourni en entree sont deja tries par abscisse croissante. En deduire que le temps d'execution total de l'algorithme de Graham-Andrew est bien majore par une constante fois n log n. 7 
