X/ENS Informatique B MP-PC 2015

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