X/ENS Informatique B MP-PC-PSI 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

X/ENS Informatique B (MP/PC) 2015 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (Enseignant-chercheur à 
l'université) ; il a été relu par Céline Chevalier (Enseignant-chercheur à 
l'université) et
Guillaume Batog (Professeur en CPGE).

Ce sujet propose l'étude de deux algorithmes calculant l'enveloppe convexe d'un
nuage de points en position générale dans le plan affine, c'est-à-dire qui ne 
contient
pas trois points distincts alignés. Le calcul d'enveloppe convexe est utilisé 
dans de
nombreux domaines : robotique, traitement d'image, théorie des jeux, 
vérification
formelle... Les parties II et III sont indépendantes.
· La première partie propose d'implémenter deux fonctions préliminaires 
permettant respectivement de trouver le point le plus bas du nuage et de tester
l'orientation d'un triangle, opération cruciale dans la suite.
· La deuxième partie étudie l'algorithme du paquet cadeau, qui consiste à 
envelopper petit à petit le nuage de points. Cette construction nécessite un 
temps
d'exécution en O(nm), où n est le nombre de points et m celui de leur enveloppe
convexe.
· Enfin, la troisième partie étudie l'algorithme de balayage qui résout le même
problème en temps O(n log n) grâce à la construction, à l'aide de piles, des 
enveloppes supérieure et inférieure des n points.
Ce sujet est d'une longueur raisonnable pour une épreuve de deux heures. Il se
concentre sur les parties d'algorithmique et de programmation du programme et ne
présente aucune difficulté majeure sous réserve de maîtriser les rudiments du 
langage
de programmation choisi.

Indications
Partie II
4 Dans la propriété d'antisymétrie, il s'agit en fait de montrer que si pj  pk 
et
pk  pj alors pj = pk : la conclusion j = k vient alors du fait que le nuage P 
est un
ensemble qui ne contient donc pas deux occurrences du même point. Pour prouver
la propriété de transitivité, utiliser le fait que pi appartient à l'enveloppe 
convexe,
de sorte que tous les autres points sont inclus dans un demi-plan contenant pi .
7 Utiliser les fonctions des questions 1 et 5. Pour ajouter un élément j à une 
liste
liste, utiliser la commande liste.append(j).
Partie III
10 Commencer par écrire une fonction auxiliaire renvoyant la paire (j, k) des 
dernier
et avant-dernier éléments de la pile, en supprimant au passage le sommet de la
pile. Utiliser alors une boucle while qui applique la fonction auxiliaire 
précédente
et teste l'orientation du triangle (pi , pj , pk ), tant que celle-ci est 
négative.
11 Se convaincre que seul le test d'orientation doit être modifié par rapport à 
la
question précédente.
12 Une fois obtenues les piles es et ei contenant les enveloppes supérieure et 
inférieure respectivement, il s'agit d'insérer à l'envers le contenu de es 
duquel on a
retiré les premier et dernier éléments à la pile ei (pour éviter les doublons).
13 Borner le nombre de fois où chaque indice peut être inséré ou supprimé 
définitivement des deux piles es et ei, puis majorer le nombre total de tests 
d'orientation
effectués le long de l'exécution de convGraham.

I. Préliminaires
1 Initialisons un indice j à 0, ayant vertu à contenir l'indice du point de 
plus petite
ordonnée. À l'aide d'une boucle for, testons chaque point afin de mettre à jour 
j si
nécessaire, à savoir si le point courant a une ordonnée strictement inférieure, 
ou bien
une même ordonnée mais une abscisse strictement inférieure.
def plusBas(tab,n):
j = 0
for i in range(1,n):
if (tab[1][i] < tab[1][j] or
(tab[1][i] == tab[1][j] and tab[0][i] < tab[0][j])):
j = i
return j
2 Pour i = 0, j = 3, k = 4, le tableau de l'énoncé apporte les coordonnées 
suivantes : le point p0 a pour coordonnées (0, 0), le point p3 a pour 
coordonnées (4, 1)

--
et le point p4 a pour coordonnées (4, 4). Ainsi, les vecteurs -
p-
0 p3 et p0 p4 ont pour
coordonnées respectives (4, 1) et (4, 4). L'aire signée du triangle (p0 , p3 , 
p4 ) est donc
1
4
×
1
2

16 - 4
4
=
=6>0
4
2

de sorte que le triangle (p0 , p3 , p4 ) est orienté positivement.
Le résultat du test d'orientation sur (p0 , p3 , p4 ) est +1.
De même, pour i = 8, j = 9, k = 10, le point p8 a pour coordonnées (7, 2),
le point p9 a pour coordonnées (8, 5) et le point p10 a pour coordonnées (11, 
6).
 ---
Par conséquent, les vecteurs -
p-
8 p9 et p8 p10 ont pour coordonnées respectives (1, 3) et
(4, 4). L'aire signée du triangle (p8 , p9 , p10 ) est ainsi
1
4 - 12
1 4
×
=
= -4 < 0
3
4
2
2
ce qui implique que le triangle (p8 , p9 , p10 ) est orienté négativement.
Le résultat du test d'orientation sur (p8 , p9 , p10 ) est -1.
3 La fonction orient calcule le déterminant utilisé dans l'aire signée du 
triangle
(pi , pj , pk ) et teste son signe. En particulier, le déterminant est nul si 
et seulement
si deux des trois points au moins sont confondus, auquel cas le résultat du test
d'orientation est 0.
def orient(tab,i,j,k):
pi_pj = [tab[0][j]-tab[0][i], tab[1][j]-tab[1][i]]
pi_pk = [tab[0][k]-tab[0][i], tab[1][k]-tab[1][i]]
det = pi_pj[0] * pi_pk[1] - pi_pj[1] * pi_pk[0]
if det > 0:
return 1
elif det < 0:
return -1
else:
return 0

II. Algorithme du paquet cadeau
4 Pour la réflexivité, notons que pour tout j 6= i, orient(tab, i, j, j) = 0 
puisque
deux des points sont égaux, de sorte que pj  pj .
Pour l'antisymétrie, supposons fixés j et k tels que pj , pk  P r {pi }, pj  pk 
et
pk  pj . Par définition,
det(-
p-
p ,-
p-
p ) 6 0 et det(-
p-
p ,-
p-
p )60
i j

i k

i k

i j

Puisque ces deux déterminants sont opposés l'un de l'autre, ils sont nuls, ce 
qui
 --
prouve que les vecteurs -
p-
i pj et pi pk sont colinéaires, c'est-à-dire que pi , pj et pk sont
alignés. Grâce à l'hypothèse de position générale et le fait que pj et pk sont 
distincts
de pi , cela montre que pj = pk .
Une coquille s'est glissée dans l'énoncé : la propriété d'antisymétrie consiste
à montrer a priori que pj  pk et pk  pj implique pj = pk , et non j = k.
On peut cependant conclure que j = k puisque le nuage P est un ensemble
qui ne contient donc pas deux occurrences du même point.
Montrons la transitivité . Pour cela, fixons j, k,  tels que pj , pk , p  P r 
{pi },
pj  pk et pk  p . Supposons également que le point pi appartient à l'enveloppe
convexe de P, de sorte que les points pj , pk et p sont tous dans un demi-plan 
dont
la frontière D contient pi (et aucun des trois autres points grâce à 
l'hypothèse de
position générale), comme représenté dans la figure de gauche ci-dessous.
D
p

-

pk

p

-

e1

-

e2

pi

-

pk

pi

+

-

-

pj

pj

La figure de droite ci-dessus montre que la propriété de transitivité est fausse
si pi n'est pas sur l'enveloppe convexe de P, puisque (pi , pj , pk ) et (pi , 
pk , p )
sont orientés négativement, mais que (pi , pj , p ) est orienté positivement.

Munissons le plan affine d'un repère orthonormé direct (pi , -
e1 , -
e2 ) avec -
e1 un vecteur

-
directeur de la droite D et e orienté vers le demi-plan contenant les points p 
, p
j

2

k

et p . Dans le plan complexe associé, les arguments principaux respectifs j , k 
et 
des points pj , pk et p appartiennent à [ 0 ;  ]. L'interprétation géométrique 
du déterminant de deux vecteurs dans le plan euclidien assure que
k-
p-
p k × k-
p-
p k × sin( -  ) 6 0 et k-
p-
p k × k-
p-
p k × sin( -  ) 6 0
i j

i k

k

j

i k

i 

k

Puisque k -j et  -k appartiennent à [ - ;  ], le fait que le sinus de ces 
angles soit
négatif implique que k - j et  - k appartiennent en fait à [ - ; 0 ]. Par somme,
 - j  [ -2 ; 0 ]. Comme cet angle est par ailleurs inclus dans [ - ;  ], on en
déduit que  - j  [ - ; 0 ], de sorte que sin( - j ) 6 0. Finalement,
det(-
p-
p ,-
p-
p ) = k-
p-
p k × k-
p-
p k × sin( -  ) 6 0
i j

i 

i j

i 

j

ce qui prouve que pj  p .
Voici une autre preuve utilisant la bilinéarité du déterminant. Les hypothèses
d'orientation négative impliquent que