Projet de Géométrie & Algorithmes
Droites et longs chemins...
Bienvenue sur ce site, qui vulgarise deux articles sur les longs chemins dans des arrangements de droite! Nous vous invitons à commencer par l'introduction et vous laisser guider par les liens, ou à faire votre choix dans la liste d'articles qui suit:
Sur ce site...
Graphe dual et plus long chemin garanti
Comme nous l'expliquions dans l'introduction, nous nous attardons sur deux cas précis de graphes définissable depuis un arrangement de droite.
Graphe primal et plus long chemin imaginable
Comme nous l'expliquions dans l'introduction, nous nous attardons sur deux cas précis de graphes définissables depuis un arrangement de droites.
Concept de la dualité
De manière générale, les représentations de deux problèmes sont dites duales si il existe un lien intrinsèque entre elles de telle manière à ce que chaque instance du premier type possède une instance du second type, calculables facilement à partir de l'autre, et dont les solutions sont elles-aussi liées par ce lien facilement calculable.
De quels longs chemins parle-t-on?
Dans ce travail, nous allons considérer la question des longs chemins dans des arrangements de droites. Un arrangement de droites, ce n'est rien de plus qu'un espace 2D dans lequel on a dessiné une série de droites. On dit que ces droites sont en position générale lorsqu'elles se croisent toutes deux à deux et qu'aucun triplet de droites ne possède d'intersection commune.
Graphe planaire depuis un arrangement de droite
Pour représenter visuellement ce problème, il faut donc pouvoir représenter de manière logicielle un arrangement de droites et le graphe dual (ou graphe des cellules) associés. Autrement dit : à partir d'un arrangement de n droites en position générale, calculer le graphe dual.