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
