Polygone simpleEn géométrie, un polygone est dit simple si deux côtés non consécutifs ne se rencontrent pas et deux côtés consécutifs n'ont en commun que l'un de leurs sommets, autrement dit, si ses segments forment une courbe de Jordan. Un polygone simple est topologiquement équivalent à un cercle. Les polygones simples sont aussi appelés « polygones de Jordan », en relation avec le théorème de Jordan qui établit que toute courbe fermée du plan qui « ne se recoupe pas » divise le plan en deux régions : l'intérieur et l'extérieur.
Problème de la galerie d'artvignette|Un polygone simple à 43 côtés représentant une galerie d'art, et quatre caméras couvrent cette galerie. En informatique, plus précisément en géométrie algorithmique, le problème de la galerie d'art est un problème de visibilité bien étudié inspiré d'un problème réel. Il se formule comme suit : « Quel est le nombre de gardiens (ou caméras) nécessaires pour surveiller une galerie d'art, et où faut-il les placer ? » Formellement, la galerie d'art est représenté par un polygone simple et chaque gardien par un point du polygone.
Graphe dualEn théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual.
Triangulation (géométrie)En géométrie, une triangulation est une partition d'un objet en un ensemble de simplexes. En particulier dans le plan, une triangulation est composée de triangles. Une triangulation est un complexe simplicial. Une triangulation d'un ensemble est une partition de en simplexes de dimension (n+1) telle que : l'intersection de deux simplexes est soit une face commune aux deux simplexes, soit vide tout ensemble borné de coupe un nombre fini de simplexes de T l'union des simplexes correspond à Un problème de géométrie est de trouver rapidement une triangulation d'un polygone, c'est-à-dire un ensemble de triangles disjoints dont l'union recouvre le polygone.
Géométrie algorithmiquevignette|Rendu d'un cylindre à l'aide d'un programme d'ordinateur. La géométrie algorithmique est le domaine de l'algorithmique qui traite des algorithmes manipulant des concepts géométriques. La géométrie algorithmique est l'étude des algorithmes manipulant des objets géométriques. Par exemple, le problème algorithmique qui consiste, étant donné un ensemble de points dans le plan décrits par leurs coordonnées, à trouver la paire de points dont la distance est minimale est un problème d'algorithmique géométrique.
Polygone convexeEn géométrie, un polygone convexe est un polygone simple dont l'intérieur est un ensemble convexe. Un polygone simple qui n'est pas convexe est dit concave. Pour un polygone simple, les propriétés suivantes sont équivalentes : le polygone est convexe, les angles du polygone sont tous inférieurs à 180 degrés, tout segment joignant deux sommets du polygone est inclus dans la composante fermée bornée délimitée par le polygone. Le polygone est toujours entièrement inclus dans un demi-plan dont la frontière porte un côté quelconque du polygone.
Triangulation de DelaunayEn mathématiques et plus particulièrement en géométrie algorithmique, la triangulation de Delaunay d'un ensemble P de points du plan est une triangulation DT(P) telle qu'aucun point de P n'est à l'intérieur du cercle circonscrit d'un des triangles de DT(P). Les triangulations de Delaunay maximisent le plus petit angle de l'ensemble des angles des triangles, évitant ainsi les triangles « allongés ». Cette triangulation a été inventée par le mathématicien russe Boris Delaunay, dans un article publié en 1924.
Sommet (géométrie)vignette|droite|Le sommet d'un angle est le point d'intersection où se réunissent deux segments de droites. En géométrie, un sommet est un point particulier d'une figure : un sommet d'un polygone, d'un polyèdre, ou plus généralement d'un polytope, est un 0-simplexe de celui-ci ; c'est l'extrémité d'au moins une arête (par analogie, on parle aussi de sommets en théorie des graphes) ; dans un polyèdre, en chaque sommet, convergent au moins trois faces et un nombre égal d'arêtes (voir aussi le théorème de Descartes-Euler, qui relie le nombre de sommets, d'arêtes et de faces d'un polyèdre) ; le sommet d'un angle est le point d'intersection des deux côtés de cet angle ; le sommet d'un cône est le point d'intersection de toutes les génératrices de ce cône.
Graphe planaireDans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.
PolygoneUn polygone, en géométrie euclidienne, est une figure géométrique plane formée d'une ligne brisée (appelée aussi ligne polygonale) fermée, c'est-à-dire d'une suite cyclique de segments consécutifs. Les segments sont appelés bords ou côtés et les extrémités des côtés sont appelés sommets ou coins du polygone. Un polygone est dit croisé si au moins deux côtés non consécutifs sont sécants, et simple si l'intersection de deux côtés est vide ou réduite à un sommet pour deux côtés consécutifs.
