Théorème de Pick - Pick's theorem

i = 7 , b = 8 , A = i + b/2 − 1 = 10

En géométrie , le théorème de Pick fournit une formule pour l' aire d'un polygone simple avec des coordonnées de sommet entières , en termes de nombre de points entiers à l'intérieur et sur sa frontière. Le résultat a été décrit pour la première fois par Georg Alexander Pick en 1899. Il a été popularisé en anglais par Hugo Steinhaus dans l'édition 1950 de son livre Mathematical Snapshots . Il a de multiples preuves et peut être généralisé à des formules pour certains types de polygones non simples.

Formule

Supposons qu'un polygone ait des coordonnées entières pour tous ses sommets. Soit le nombre de points entiers qui sont à l'intérieur du polygone, et soit le nombre de points entiers sur sa frontière (y compris les sommets ainsi que les points le long des côtés du polygone). Alors l' aire de ce polygone est :

L'exemple montré a des points intérieurs et des points limites, donc son aire est en unités carrées.

Preuves

Par la formule d'Euler

Une preuve de ce théorème consiste à subdiviser le polygone en triangles avec trois sommets entiers et aucun autre point entier. On peut alors prouver que chaque triangle subdivisé a exactement une aire . Par conséquent, l'aire du polygone entier est égale à la moitié du nombre de triangles de la subdivision. Après avoir lié l'aire au nombre de triangles de cette manière, la preuve se termine en utilisant la formule polyédrique d'Euler pour relier le nombre de triangles au nombre de points de grille dans le polygone.

Pavage du plan par des copies d'un triangle avec trois sommets entiers et aucun autre point entier, comme utilisé dans la preuve du théorème de Pick

La première partie de cette preuve montre qu'un triangle avec trois sommets entiers et aucun autre point entier a exactement une aire , comme l'indique la formule de Pick. La preuve utilise le fait que tous les triangles tuiles le plan , avec des triangles adjacents tournés de 180° les uns par rapport aux autres autour de leur bord commun. Pour les pavages par un triangle avec trois sommets entiers et aucun autre point entier, chaque point de la grille entière est un sommet de six carreaux. Comme le nombre de triangles par point de grille (six) est le double du nombre de points de grille par triangle (trois), les triangles sont deux fois plus denses dans le plan que les points de grille. Toute région mise à l'échelle du plan contient deux fois plus de triangles (dans la limite où le facteur d'échelle tend vers l'infini) que le nombre de points de grille qu'elle contient. Par conséquent, chaque triangle a une aire , comme nécessaire pour la preuve. Une preuve différente que ces triangles ont une aire est basée sur l'utilisation du théorème de Minkowski sur les points du réseau dans les ensembles convexes symétriques.

Subdivision d'un polygone de grille en triangles spéciaux

Cela prouve déjà la formule de Pick pour un polygone qui est l'un de ces triangles spéciaux. Tout autre polygone peut être subdivisé en triangles spéciaux. Pour ce faire, ajoutez des segments de ligne qui ne se croisent pas dans le polygone entre des paires de points de grille jusqu'à ce qu'aucun autre segment de ligne ne puisse être ajouté. Les seuls polygones qui ne peuvent pas être subdivisés en formes plus petites de cette manière sont les triangles spéciaux considérés ci-dessus. Par conséquent, seuls des triangles spéciaux peuvent apparaître dans la subdivision résultante. Parce que chaque triangle spécial a une aire , un polygone d'aire sera subdivisé en triangles spéciaux.

La subdivision du polygone en triangles forme un graphe planaire et la formule d'Euler donne une équation qui s'applique au nombre de sommets, d'arêtes et de faces de tout graphe planaire. Les sommets ne sont que les points de grille du polygone ; il y en a. Les faces sont les triangles de la subdivision et la seule région du plan à l'extérieur du polygone. Le nombre de triangles est , donc en tout il y a des faces. Pour compter les arêtes, observez qu'il y a des côtés de triangles dans la subdivision. Chaque bord intérieur au polygone est le côté de deux triangles. Cependant, il y a des arêtes de triangles qui se trouvent le long de la limite du polygone et font partie d'un seul triangle. Par conséquent, le nombre de côtés des triangles obéit à une équation à partir de laquelle on peut résoudre pour le nombre d'arêtes, . Le fait de brancher ces valeurs pour , , et dans la formule d'Euler donne

La formule de Pick peut être obtenue en simplifiant cette équation linéaire et en résolvant . Un autre calcul dans le même sens consiste à prouver que le nombre d'arêtes d'une même subdivision est égal à , conduisant au même résultat.

Il est également possible d'aller dans l'autre sens, en utilisant le théorème de Pick (démontré d'une manière différente) comme base d'une preuve de la formule d'Euler.

Autres preuves

Les preuves alternatives du théorème de Pick qui n'utilisent pas la formule d'Euler sont les suivantes.

  • On peut décomposer récursivement le polygone donné en triangles, permettant à certains triangles de la subdivision d'avoir une aire supérieure à 1/2. L'aire et le nombre de points utilisés dans la formule de Pick s'additionnent de la même manière, de sorte que la vérité de la formule de Pick pour les polygones généraux découle de sa vérité pour les triangles. Tout triangle subdivise sa zone de délimitation dans le triangle lui - même et d' autres triangles , et les zones à la fois la zone de délimitation et les triangles sont faciles à calculer. La combinaison de ces calculs de surface donne la formule de Pick pour les triangles, et la combinaison de triangles donne la formule de Pick pour les polygones arbitraires.
  • Le diagramme de Voronoï de la grille entière subdivise le plan en carrés, centrés autour de chaque point de la grille. On peut calculer l'aire de n'importe quel polygone comme la somme de ses aires dans chaque cellule de ce diagramme. Pour chaque point de grille intérieur du polygone, toute la cellule de Voronoï est couverte par le polygone. Les points de grille sur un bord du polygone ont la moitié de leur cellule de Voronoï couverte. Les cellules de Voronoï des points d'angle sont couvertes par des montants dont les différences entre un demi-carré (en utilisant un argument basé sur le nombre de tours ) totalisent le terme de correction dans la formule de Pick.
  • Alternativement, au lieu d'utiliser des carrés de grille centrés sur les points de grille, il est possible d'utiliser des carrés de grille ayant leurs sommets aux points de grille. Ces carrés de grille coupent le polygone donné en morceaux, qui peuvent être réorganisés (en faisant correspondre des paires de carrés le long de chaque bord du polygone) en un polyomino de même surface.
  • Le théorème de Pick peut également être prouvé sur la base de l' intégration complexe d'une fonction doublement périodique liée aux fonctions elliptiques de Weierstrass .
  • L'application de la formule de sommation de Poisson à la fonction caractéristique du polygone conduit à une autre preuve.

Le théorème de Pick a été inclus dans une liste Web des « 100 meilleurs théorèmes mathématiques », datant de 1999, qui a ensuite été utilisé par Freek Wiedijk comme ensemble de référence pour tester la puissance de différents assistants de preuve . En 2021, une preuve du théorème de Pick avait été formalisée dans un seul des dix assistants de preuve enregistrés par Wiedijk.

Généralisations

Des généralisations au théorème de Pick aux polygones non simples sont possibles, mais sont plus compliquées et nécessitent plus d'informations que le nombre de sommets intérieurs et limites. Par exemple, un polygone avec des trous délimités par des polygones entiers simples, disjoints les uns des autres et de la frontière, a une aire

Il est également possible de généraliser le théorème de Pick aux régions délimitées par des graphes linéaires planaires plus complexes avec des coordonnées de sommet entières, en utilisant des termes supplémentaires définis à l'aide de la caractéristique d'Euler de la région et de sa frontière, ou à des polygones avec un seul polygone frontière qui peut traverser lui-même, en utilisant une formule impliquant le nombre d'enroulements du polygone autour de chaque point entier ainsi que son nombre d'enroulements total.

Les tétraèdres de Reeve en trois dimensions ont quatre points entiers comme sommets et ne contiennent aucun autre point entier. Cependant, ils n'ont pas tous le même volume les uns que les autres. Par conséquent, il ne peut y avoir d'analogue du théorème de Pick en trois dimensions qui exprime le volume d'un polytope en fonction uniquement de ses nombres de points intérieurs et limites. Cependant, ces volumes peuvent plutôt être exprimés à l'aide de polynômes d'Ehrhart .

Rubriques connexes

Plusieurs autres sujets en mathématiques relient les aires des régions au nombre de points de la grille. Parmi eux, le théorème de Blichfeldt stipule que chaque forme peut être translatée pour contenir au moins son aire en points de grille. Le problème du cercle de Gauss concerne la limitation de l'erreur entre les aires et le nombre de points de grille dans les cercles. Le problème du comptage de points entiers dans des polyèdres convexes se pose dans plusieurs domaines des mathématiques et de l'informatique. Dans les domaines d'application, le planimètre à points est un dispositif basé sur la transparence pour estimer l'aire d'une forme en comptant les points de grille qu'elle contient. La suite de Farey est une suite ordonnée de nombres rationnels à dénominateurs bornés dont l'analyse fait intervenir le théorème de Pick.

Une autre méthode simple pour calculer l'aire d'un polygone est la formule du lacet . Il donne l'aire de tout polygone simple comme une somme de termes calculée à partir des coordonnées de paires consécutives de sommets du polygone. Contrairement au théorème de Pick, il ne nécessite pas que les sommets aient des coordonnées entières.

Les références

Liens externes