Polygones convexes : le problème de la fin heureuse

Piste rouge 28 novembre 2014  - Ecrit par  Pierre-Alain Cherix, Shaula Fiorelli Vilmart, Pierre de la Harpe Voir les commentaires (3)

D’abord une observation élémentaire, puis une question plus générale, un résultat partiel, une conjecture, des pratiquants résolus de l’idée fixe, et une postérité multiforme : ce sont souvent les ingrédients d’un beau sujet mathématique.
En guise d’illustration, voici une présentation du problème de la fin heureuse, plus connu en français (et sans doute en hongrois) sous le nom du happy end problem.

Les couleurs de cet article sont le rouge pour l’essentiel avec un peu de bleu au début et du noir vers la fin. La plupart des références sont hors piste.

Trois protagonistes, Esther Klein, Paul Erdös et George Szekeres apparaissent dans le happy end problem, les voici sur la photo en logo, en Australie, plus précisément à Newcastle, en 1984.

L’observation d’Esther Klein

Commençons par un élégant énoncé
dû à une jeune mathématicienne hongroise du début des années 30, Esther Klein :

Parmi cinq points du plan en position générale,
il en existe quatre qui sont les sommets d’un quadrilatère convexe.

Avant de justifier cet énoncé, rappelons quelques notions de géométrie plane.
Un ensemble de points du plan est en position générale
lorsque trois d’entre eux ne sont jamais alignés.
Une région du plan est convexe si,
chaque fois qu’elle contient deux points distincts, elle contient aussi le segment qui les joint.
Par exemple, les trois régions que voici

JPEG - 35.3 ko
Trois régions convexes

sont convexes, et les trois que voilà

JPEG - 39.2 ko
Trois régions non convexes
On observe que le segment reliant les deux points bleus de la région de gauche n’est pas contenu dans la région.

ne le sont pas.
Rappelons aussi que toute partie du plan est contenue dans des régions convexes,
et en particulier dans une région convexe bien particulière qui est la plus petite d’entre elles,
et qu’on appelle son enveloppe convexe.
Par exemple, la partie du plan formée des points rouges de la figure suivante
est contenue dans son enveloppe convexe qui est le polygone à bord bleu.

JPEG - 32.8 ko
Enveloppe convexe bleue d’une partie formée de points rouges

Construction de l’enveloppe convexe

Voici un algorithme simple et visuel pour construire l’enveloppe convexe d’une famille finie de points $P_1$, …,$P_n$, et une animation pour l’illustrer.

On choisit au hasard une droite $d$ telle que toute la famille de points soit dans un des demi-plans défini par $d$. On translate cette droite jusqu’au moment où celle-ci rencontre un des points $P_i$. On choisit un sens de rotation (par exemple le sens positif) et on fait tourner la droite parallèle à $d$ passant par $P_i$ autour de ce point $P_i$. On arrête la rotation de la droite dès que celle-ci rencontre un autre point $P_j$. Le segment $[P_i ;P_j]$ reliant ces deux points fait partie de l’enveloppe convexe de la famille. En effet, tous les points de la famille sont dans un des deux demi-plans définis par cette droite.
On fait maintenant tourner la droite $P_i P_j$ autour du deuxième point $P_j$ dans le même sens que précédemment jusqu’à rencontrer un troisième point $P_k$ de la famille. A nouveau le segment $[P_j ;P_k]$ est dans le bord de l’enveloppe convexe. On continue ainsi de suite jusqu’à retrouver le point $P_i$ de départ.
La suite des segments ainsi définis délimite bien l’enveloppe convexe de la famille.

La littérature spécialisée consacrée à ce genre d’algorithmes est abondante ;
nous avons suivi (à peu près) un article de Jarvis qu’on trouve en ligne [1].

IMG/html/enveloppe2_6.html
Construction de l’enveloppe convexe bleue d’une partie formée de points rouges
Créé avec GeoGebra

Voici la démonstration, élémentaire, de l’énoncé d’Esther Klein.

On se donne $5$ points du plan en position générale. Leur enveloppe convexe est un polygone dont on note $k$ le nombre des sommets.
Si $k=4$, il n’y a plus rien à montrer.
Si $k = 5$, tout choix de $4$ de ces sommets fournit un quadrilatère convexe.
Le seul cas qui mérite encore un argument est donc celui où l’enveloppe convexe
des $5$ points donnés est un triangle ($k=3$), ce que nous supposons désormais.
Notons $A, B, C$ les sommets de ce triangle, et $D, E$ les deux autres points donnés,
qui sont à l’intérieur du triangle.
Notons encore $\ell$ la droite passant par $D$ et $E$.
Vu l’hypothèse de position générale,
la droite $\ell$ ne passe par aucun des sommets $A, B, C$.
Comme elle ne peut pas couper les trois côtés du triangle,
il existe deux sommets situés du même côté de $\ell$ ;
supposons les notations telles que ce soient $B$ et $C$.
Alors $B, C, D, E$ sont les sommets d’un quadrilatère convexe. La démonstration est ainsi achevée.

JPEG - 55.3 ko
Illustration de la démonstration

Le premier article : Paul Erdös et George Szekeres

La Budapest des années 30 foisonnait de jeunes mathématiciens brillants.
Celui qui est devenu le plus célèbre est Paul Erdös (1913—1996).
Il y avait aussi Paul Turan (1910—1976), Esther Klein (1910—2005),
George Szekeres (1911—2005), et bien d’autres.
L’observation d’Esther eut plusieurs suites :
en 1935 un article marquant d’Erdös et Szekeres,
et peut-être aussi en 1937 le mariage d’Esther et George,
ou Eszter et György ;
d’où la terminologie du « happy end problem », due à Erdös.

Leurs carrières ne furent pas banales.
Bien que passionnés de mathématiques,
George Szekeres fit des études de chimie
(son père espérait qu’il contribue à l’affaire de la famille, dans le cuir),
et Esther Klein de physique
(Esther ayant le double handicap d’être femme et juive, elle dut laisser
« la » place d’étudiante en mathématique à son amie Marta Sved).

Après avoir échappé in extremis aux persécutions nazies à Budapest
et aux bombes japonaises sur Shanghai, les Szekeres s’établirent en Australie en 1948, où ils furent d’abord hébergés par les Sved.
George Szekeres y fut un mathématicien productif et influent jusqu’au début des années 2000 (il n’avait pourtant jamais obtenu de diplôme en mathématiques !).
Ses sujets principaux de recherche furent la combinatoire, la géométrie,
et la relativité générale.
Dès 1964, il fut à Sydney le professeur fondateur du département de mathématiques fondamentales de l’Université de New South Wales [2].
En 1998, l’un de nous occupa un bureau à côté du sien,
d’où il entendait l’après-midi George et Esther dans leur duo de violons.
Esther Szekeres enseigna à l’Université Macquarie,
et s’investit beaucoup dans la stimulation mathématique des collégiens et lycéens. La base de données MathSciNet recense pour elle deux articles de recherche en mathématiques.

Le « happy end » dura : Esther et George moururent
de vieillesse à une heure d’intervalle.

Quant à Paul Erdös, il détient de nombreux records, dont celui du plus grand
nombre d’articles publiés (1421 dans la liste de MathSciNet au jour de notre dernier pointage),
et du plus grand nombre de co-auteurs (498 selon la même base de données).
On entretient à son sujet les légendes les plus incroyables,
et souvent vraies
 [3].

Les triangles et les quadrilatères sont les deux premières espèces
d’une population qui comprend des pentagones (polygones à $k=5$ côtés),
les hexagones ($k=6)$, les heptagones ($k=7$), ...

JPEG - 25.1 ko
Un heptagone convexe

Lorsqu’on veut préciser qu’un certain polygone a exactement $k$ côtés,
on dit que c’est un $k$-gone.

L’article d’Erdös et Szekeres de 1935
 [4],
Compositio Math. 2 (1935), 463-470, énonce la généralisation « évidente » suivante du problème d’Esther Klein :

Pour un nombre donné $k$, peut-on trouver un nombre $N$ (dépendant de $k$)
tel que, de toute partie du plan contenant au moins $N$ points en position générale,
on puisse en choisir $k$ qui soient les sommets d’un $k$-gone convexe ?

Il y a en fait plusieurs questions : d’abord existe-t-il un tel $N$ ?
et si oui quelle est sa plus petite valeur possible, notée $N(k)$ ci-dessous ?
à défaut, peut-on au moins l’estimer ?

Théorème d’Erdös et Szekeres.
Pour tout $k \ge 3$, il existe un nombre entier $N(k)$
qui a les propriétés suivantes :

  1. Soit $X$ un ensemble de $n$ points dans le plan, en position générale.
    Si $n \ge N(k)$, il existe $k$ points dans $X$ qui sont les sommets
    d’un $k$-gone convexe.
  2. Dans 1. l’entier $N(k)$ ne peut pas être remplacé par un entier strictement plus petit.

L’article original offre deux démonstrations,
chacune fournissant pour tout $k$ une borne, c’est-à-dire une majoration de $N(k)$.
Mais ces bornes ne sont pas optimales, loin s’en faut.
Ainsi, pour $k=5$, la première borne est de l’ordre de $2^{10 000}$
(en anticipant une notation introduite plus bas,
disons que cette borne résulte de l’inégalité $N(k) \le R_4(5, k)$).
La seconde borne est $21$. Or un collègue d’Erdös et Szekeres
avait déjà montré en 1935 que la meilleure borne possible est $N(5)=9$.

Même s’il suffit souvent de savoir que le nombre $N(k)$ existe
et d’en connaître un majorant,
il est bien naturel de vouloir déterminer sa valeur exacte.
La conjecture qui suit, due à Erdös et Szekeres,
repose sur leur conviction, pour nous à la fois éclairée et mystérieuse ;
elle est vieille de 80 ans, et toujours ouverte :

\[ N(k) = 2^{k-2} + 1 \hskip.5cm \text{(non démontré)} \]

pour tout $k \ge 3$.
Par exemple, pour $k=7$, personne n’a encore pu montrer que,
dans tout ensemble de 33 points en position générale,
on peut toujours en trouver $7$ qui sont les sommets d’un heptagone convexe.

Quelques progrès

Autant que nous sachions, les seuls cas pour lesquels nous connaissions
exactement $N(k)$ aujourd’hui sont ceux pour lesquels $k \le 6$.
Plus précisément, en plus de l’égalité banale $N(3) = 3$ :

\[ N(4) = 5, \ N(5) = 9 \,\text{ et }\, N(6) = 17 . \]

La valeur $17$ pour $k=6$ fut établie par Szekeres lui-même
(avec son collègue Peters et un ordinateur bien programmé),
dans un article rédigé peu avant sa mort et paru en 2006,
septante ans après le premier article !
Bel exemple d’idée fixe (et fructueuse).

Vingt-cinq ans après leur premier article sur le sujet,
Erdös et Szekeres en publièrent un second
 [5],
dans lequel ils exhibent pour tout $k \ge 4$ un ensemble de $2^{k-2}$ points
en position générale sans qu’il existe $k$ de ces points
qui soient les sommets d’un $k$-gone convexe.
Il en résulte que $2^{k-2}+1 \le N(k)$.

JPEG - 22.7 ko
Quatre points qui ne sont pas les sommets d’un quadrilatère convexe

IMG/html/fig5_8ptsbanim_3.html
Huit points parmi lesquels on ne peut pas en trouver cinq qui soient les sommets d’un pentagone convexe
En bougeant le curseur, on peut voir quelques-uns des 56 pentagones possibles.
La position 0 montre la configuration initiale des 8 points et leur enveloppe convexe.
Créé avec GeoGebra

IMG/html/fig5_16points.html
Seize points parmi lesquels on ne peut pas en trouver six qui soient les sommets d’un hexagone convexe
En bougeant le curseur, on peut voir quelques-uns des 8008 hexagones non convexes.
La position 0 montre la configuration initiale des 16 points et leur enveloppe convexe.
Créé avec GeoGebra

Il existe aussi des majorations, de sorte qu’on sait
par exemple que

\[ 262.645 \le N(20) \le 4.537.567.650 \]

pour $k=20$, et en général que

\[ 2^{k-2} + 1 \le N(k) \le \binom{2k-5}{k-2} + 1 \]

pour tout $k \ge 5$.

Au membre de droite apparaît un coefficient binomial
de la forme $\binom{a}{b}$, où $a$ et $b$ sont deux nombres entiers
tels que $a \ge b \ge 0$ ;
par définition $\binom{a}{b} = \frac{a!}{b! (a-b)!}$.
Le point d’exclamation
désigne une factorielle : $a! = a (a-1) (a-2) \cdots 2 \cdot 1$ ;
par exemple $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ et

\[ \binom{7}{4} \, = \, \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} {4 \cdot 3 \cdot 2 \cdot 1 \hskip.1cm \cdot \hskip.1cm 3 \cdot 2 \cdot 1} \, = \, \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} \, = \, 35 . \]

La borne supérieure pour $N(k)$ a péniblement progressé :
par exemple $\binom{2k-4}{k-2}+1$ en 1935,
$\binom{2k-4}{k-2}$ en 1998 (Chung et Graham, 63 ans pour cette petite amélioration,
mais une nouvelle idée),
$\binom{2k-5}{k-2}+2$ en 1998 (Tóth et Valtr),
et $\binom{2k-5}{k-2}+1$ en 2005 (les mêmes).

On est encore loin de la valeur conjecturée $2^{k-2}+1$,
puisque

\[ \binom{2k-5}{k-2} \, \approx \, \frac{1}{ \sqrt{\pi k} } 2^{2k-5} \, >> \, 2^{k-2}+1 . \]

Le signe $\approx$ indique que les termes à gauche et à droite ont le même ordre de grandeur
pour $k$ grand,
et le signe $>>$ se lit « beaucoup plus grand que ».

Théorie de Ramsey

L’article initial d’Erdös et Szekeres fut un point de départ
pour de nombreux travaux et résultats, dans plusieurs sujets.
Parmi eux la géométrie combinatoire,
dont nous ne dirons rien sinon
que c’est un sujet d’origine assez récente
qui regorge de problèmes ouverts captivants
 [6].
Et aussi la théorie de Ramsey, sur laquelle nous
avons choisi d’en dire un peu plus.

Frank Plumpton Ramsey fut une étoile filante. Anglais, né en 1903, il étudia les mathématiques à Cambridge, fut aussi étudiant de l’économiste Keynes, avait une connaissance encyclopédique de la littérature anglaise, et entreprit à Vienne une psychanalyse avec un disciple de Freud.
C’est à Vienne qu’il rencontra le philosophe Wittgenstein,
dont il fut plus tard le directeur de thèse à Cambridge.
Ramsey mourut à 26 ans.
Ses écrits vont de la logique mathématique à l’économie en passant par la philosophie.
Aujourd’hui, on s’en souvient surtout par un théorème qui fut d’abord
un lemme mineur dans un article de logique formelle paru en 1930.
Voici un cas particulier des énoncés tels qu’on les connaît aujourd’hui.
Pour une paraphrase des formulations de Ramsey
qui soit plus fidèle à l’original mais néanmoins en langage moderne
(et toutefois largement hors-piste), voir la section 1.7 de
 [7].

Théorème de Ramsey.
Soit $p, q, r$ des entiers tels que $p \ge r \ge 1$ et $q \ge r$.
Il existe un entier $R_r(p, q)$ qui a les propriétés suivantes :

  1. Soit $X$ un ensemble fini à $n \ge \max \{p,q\}$ éléments
    et $S$ l’ensemble de ses parties à $r$ éléments.
    On suppose de plus $S$ divisé en deux parties disjointes, $T$ et $U$.
    Alors, si $n \ge R_r(p, q)$, l’une au moins des propriétés suivantes est satisfaite :
    • il existe une partie $P$ de $X$ à $p$ éléments telle que toute partie de $P$ à $r$ éléments est dans $T$,
    • il existe une partie $Q$ de $X$ à $q$ éléments telle que toute partie de $Q$ à $r$ éléments est dans $U$.
  2. Dans 1. l’entier $R_r(p, q)$ ne peut pas être remplacé par un entier strictement plus petit.

En d’autres termes, si on cherche un peu d’ordre ($r$ éléments tous de la même espèce) et qu’on a des ambitions limitées, on est sûr de le trouver ($P$ ou $Q$) dans tout désordre suffisamment grand ($X$ avec au moins $R_r(p,q)$ éléments).

Notons que, même si on ne s’intéresse qu’aux nombres de Ramsey
pour lesquels $p=q$, les démonstrations que nous connaissons
procèdent par récurrence sur $r$, $p$ et $q$, et font intervenir des nombres
avec $p \ne q$. L’essentiel de la démonstration du Théorème de Ramsey consiste à montrer que

\[ R_r(p,q) \, \le \, R_{r-1}\left( R_r(p-1,q), R_r(p,q-1) \right) + 1 . \]

Par exemple :

\[ R_2(p,q) \, \le \, R_1(R_2(p-1,q), R_2(p,q-1)) +1 = R_2(p-1,q) + R_2(p,q-1) \]

pour tous $p,q \ge 2$.
(Pour en voir un peu plus, signalons le livre
 [8].)

Quelques égalités portant sur ces nombres de Ramsey sont faciles à déterminer.
Ainsi : $R_r(q,p) = R_r(p,q)$ pour tous $p,q,r$ avec $p,q \ge r \ge 1$.
Notons aussi que $R_1(p,q) = p+q-1$ pour tous $p,q \ge 1$ ;
par exemple, si je veux sortir à l’aveugle d’un tiroir contenant des chaussettes rouges et bleues
une paire de la même couleur, il suffit toujours que je sorte $R_1(2,2) = 3$ chaussettes.

Lorsque $r=2$, l’énoncé du théorème peut se reformuler comme suit.
On considère un ensemble $X$ à $n$ éléments,
vu comme les sommets d’un $n$-gone convexe.
L’ensemble $S$ s’identifie à celui des côtés et diagonales de ce polygone ;
par exemple, l’ensemble $S$ contient $10$ éléments pour un pentagone,
$15$ pour un hexagone, en général $\binom{n}{2}$ côtés et diagonales pour un $n$-gone.
La partition de $S$ s’interprète comme un coloriage de ces segments :
convenons que $T$ est l’ensemble des segments rouges et $U$ celui des segments bleus.

Il est alors presqu’évident que $R_2(p,2) = p$ pour tout $p \ge 2$.
En effet, si on colorie les segments d’un $p$-gone, ou bien ils seront tous rouges et leurs sommets constituent un ensemble rouge à $p$ éléments,
ou bien il y en a au moins un bleu dont les sommets constituent un ensemble bleu à 2 éléments.

Voici encore l’argument élémentaire classique montrant que $R_2(3,3) = 6$,
argument qui apparaît par exemple déjà
ici.
On considère l’ensemble $X$ des sommets d’un hexagone
dont les côtés et diagonales sont coloriés en rouge et en bleu ; on cherche un triangle ou bien à 3 côtés rouges ou bien à 3 côtés bleus.

JPEG - 101.5 ko
Illustration de la démonstration de $R_2(3,3) \le 6$

Soit $A$ un sommet de $X$. Comme $A$ est l’origine de cinq segments,
il en existe au moins trois de la même couleur, disons rouge
(si c’était bleu, la suite du raisonnement serait analogue).
Notons $B, C, D$ les autres sommets de ces trois segments.
Si les trois côtés du triangle de sommets $B, C, D$ sont bleus, il n’y a plus rien à montrer.
Sinon, disons que c’est le côté $BC$ qui est rouge,
et alors les trois côtés du triangle de sommets $A, B, C$ sont rouges.

Nous avons ainsi montré que $R_2(3,3) \le 6$,
et nous laissons au lecteur le soin de se convaincre que $R_2(3,3) > 5$
(en dessinant un pentagone à côtés rouges et diagonales bleues).

A part quelques cas exceptionnels, dont ceux évoqués ci-dessus,
on ne sait pas calculer les nombres $R_r(p,q)$. On sait au mieux les estimer,
et souvent de manière grossière. Par exemple, le mieux que nous sachions
concernant $R_2(5,5)$ semble être la fourchette

\[ 43 \, \le \, R_2(5,5) \, \le \, 49 , \]

malgré de très nombreux efforts pour préciser ces inégalités.
De même,

\[ 798 \, \le \, R_2(10, 10) \, \le \, 23556 \]

(d’après
 [9]
).

Le théorème de Ramsey fut l’objet
de développements et d’applications innombrables,
auxquels Erdös contribua de manière fondamentale.

À propos de la démonstration de l’existence d’une borne pour $N(k)$

Terminons par quelques indications sur la démonstration
de bornes pour les entiers $N(k)$ qui interviennent dans le théorème
d’Erdös et Szekeres.
Nous suivons le livre de van Lint et Wilson cité plus haut
plutôt que l’article original de 1935 ;
les deux sources font appel au théorème de Ramsey.
En fait, Szekeres a découvert lui-même le théorème de Ramsey,
après Ramsey mais indépendamment de lui, pour les besoins
du théorème d’Erdös et Szekeres (selon la préface d’Erdös
au livre déjà cité de Brass, Moser et Pach).

Il y a d’abord une observation élémentaire mais cruciale pour la suite :

Pour qu’un polygone à $k \ge 4$ côtés soit convexe, il faut et il suffit que
chacun des quadrilatères déterminé par $4$ de ses sommets soit convexe.

Indiquons alors comment on montre que $N(k) \le R_3(k,k)$ pour tout $k \ge 4$.
Soit $X$ un ensemble de $N = R_3(k,k)$ points en position générale
dans un plan.
Soit $S$ l’ensemble des triplets $\{A,B,C\}$ de points de $X$.
Notons $T$ l’ensemble de ces triplets pour lesquels
le triangle de sommets $A,B,C$ contient un nombre pair (peut-être nul)
de points de $X$,
et $U$ son complémentaire dans $S$.
On choisit dans $X$ un $k$-uplet $P$ de sommets dont tous les triplets sont ou bien dans $T$
ou bien dans $U$.
Aucun des quadruplets de $P$
ne fournit un triangle avec un point intérieur, comme l’indique la figure suivante,

JPEG - 65.8 ko
Illustration de la démonstration
Figure de gauche : les trois petits triangles contiennent des nombres pairs de points
(0, 2, 4, tous bleus) et le grand un nombre impair (7, point rouge compris).
Figure de droite : les trois petits triangles contiennent des nombres impairs de points
(1, 3, 5) et le grand un nombre pair (10).

Donc, chacun des quadruplets de $P$ constitue les sommets d’un quadrilatère convexe

Pour un aperçu sur les nombreuses variantes que le problème
de Klein-Erdös-Szekeres a suggérées,
nous signalons la section 8.2 du livre de Brass, Moser et Pach,
ainsi que le chapitre 3 d’un livre de J. Matousek
 [10].

Post-scriptum :

Nous remercions Janos Pach pour sa bienveillance de connaisseur du sujet et Clement_M, Loren Coquille, Jérôme Buzzi et Audibert pour leur relecture attentive.

Article édité par Jérôme Buzzi

Notes

[1Voir sur Science Direct.

[2Voir sur ce
site.

[4P. Erdös et G. Szekeres,
« A combinatorial problem in geometry ».

[5P. Erdös et G Szekeres,
« On some extremum problems in elementary geometry »,
Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3-4 (1960/1961), 53-62.

[6Voir par exemple
P. Brass, W.O.J. Moser et J. Pach,
« Research problems in discrete geometry »,
Springer, 2005
(avec une préface de P. Erdös à une édition précédente).

[7R.L. Graham, B.L. Rotschild et J.H. Spencer,
« Ramsey theory »,
Wiley-Interscience, 1980.

[8J.H. van Lint et R.M. Wilson,
« A course in combinatorics »,
Cambridge University Press, 1992.

[9S.P. Radziszowski,
« Small Ramsey numbers »,
Electron. J. Combin. 1 (1994),
Revision $\sharp$ 14, January12, 2014.

[10Jiri Matousek,
Lectures on discrete geometry,
Graduate Texts in Mathematics 212,
Springer 2002.

Partager cet article

Pour citer cet article :

Pierre-Alain Cherix, Shaula Fiorelli Vilmart, Pierre de la Harpe — «Polygones convexes : le problème de la fin heureuse» — Images des Mathématiques, CNRS, 2014

Crédits image :

Image à la une - Cultural Collections, the University of Newcastle (Australia) Library.
Trois régions convexes - Shaula Fiorelli Vilmart
Trois régions non convexes - Shaula Fiorelli Vilmart
Enveloppe convexe bleue d’une partie formée de points rouges - Shaula Fiorelli Vilmart
Illustration de la démonstration - Shaula Fiorelli Vilmart
Un heptagone convexe - Shaula Fiorelli Vilmart
Illustration de la démonstration de - Shaula Fiorelli Vilmart
Quatre points qui ne sont pas les sommets d’un quadrilatère convexe - Shaula Fiorelli Vilmart
Illustration de la démonstration - Shaula Fiorelli Vilmart
Seize points parmi lesquels on ne peut pas en trouver six qui soient les sommets d’un hexagone convexe - Pierre-Alain Cherix et Shaula Fiorelli Vilmart
Huit points parmi lesquels on ne peut pas en trouver cinq qui soient les sommets d’un pentagone convexe - Pierre-Alain Cherix et Shaula Fiorelli Vilmart
Construction de l’enveloppe convexe bleue d’une partie formée de points rouges - Pierre-Alain Cherix et Shaula Fiorelli Vilmart

Commentaire sur l'article

  • Polygones convexes : le problème de la fin heureuse

    le 8 décembre 2014 à 15:25, par Sylvain Barré

    Bonjour !
    Merci pour ce superbe article. Je me demandais pourquoi dans l’exemple donné avec 8 sommets les points étaient si proches d’être alignés... alors j’ai cherché toutes les solutions symétriques (deux carrés l’un dans l’autre, de même centre). C’est un exercice amusant qui donne une belle rosace délimitée par des arcs de cercle, et j’ai compris. Trop beau !

    Répondre à ce message
  • Polygones convexes : le problème de la fin heureuse

    le 13 janvier 2015 à 16:58, par Limeme

    Bonjour, Merci c’est un article très intéressant.

    • j’ai une question a propos les polygones convexes, Comment peut on identifier les points de bord(points extrêmes) d’un polygone convexe, Car on peut se limiter a cet ensemble des points pour déterminer l’enveloppe convexe du polygone on gagnant en temps et en espace (complexité).
    • Dans un deuxième temps je cherche un algorithme qui permet de calculer l’intersection de deux polygones convexes

      N.B Un polygone est donnée comme étant un ensemble de point a coordonnées entière (dans mon cas).

    Si quelqu’un peut m’aider je serai reconnaissant
    Merci d’avance.

    Répondre à ce message
  • Polygones convexes : le problème de la fin heureuse

    le 16 janvier 2015 à 15:22, par Pierre de la Harpe

    Bien que parfaitement incompétent, voici ce que je peux imaginer.

    Soient $P$ et $Q$ deux polygones convexes dans un même plan.
    Il existe donc des demi-plans fermés $D_1, D_2, ..., D_k, E_1, E_2, …, E_\ell$
    tels que $P$ soit l’intersection des $D_i$ et $Q$ l’intersection des $E_j$.
    L’intersection de $P$ et $Q$ est dans ce cas le polygone convexe (ou l’ensemble vide)
    intersection des $k+\ell$ demi-plans $D_1, D_2, ..., E_\ell$.
    Je ne connais rien au sujet, mais je suppose qu’il n’est pas bien difficile
    de programmer une machine, c’est-à-dire d’écrire et implémenter un algorithme,
    pour réaliser cela.

    On peut aussi proposer à un moteur de recherche une suite de mots, préférablement en anglais, du genre
    « convex polygon intersection algorithm ». Parmi les pages proposées par google (par exemple),
    il y aura sans doute du bon grain, même s’il faut s’attendre à un peu d’ivraie.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM