Der Satz von Pick - Pick's theorem

In der Geometrie , der Satz von Pick liefert eine Formel für die Fläche eines einfachen Polygons mit ganzzahligen Scheitelkoordinaten in Bezug auf die Anzahl der Gitterpunkte in sich und auf seinem Rand. Das Ergebnis wurde erstmals 1899 von Georg Alexander Pick beschrieben. Auf Englisch wurde es von Hugo Steinhaus in der 1950er Ausgabe seines Buches Mathematical Snapshots populär gemacht . Es hat mehrere Beweise und kann auf Formeln für bestimmte Arten von nicht einfachen Polygonen verallgemeinert werden.

Formel

Angenommen, ein Polygon hat ganzzahlige Koordinaten für alle seine Scheitelpunkte. Sei die Anzahl der ganzzahligen Punkte im Inneren des Polygons und die Anzahl der ganzzahligen Punkte an seiner Grenze (einschließlich Scheitelpunkten sowie Punkten entlang der Seiten des Polygons). Dann ist die Fläche dieses Polygons: ${\displaystyle i}$${\displaystyle b}$ ${\displaystyle A}$

Das gezeigte Beispiel hat innere Punkte und Randpunkte, daher ist seine Fläche quadratische Einheiten. ${\displaystyle i=7}$${\displaystyle b=8}$${\displaystyle A=7+{\tfrac {8}{2}}-1=10}$

Beweise

Über die Eulersche Formel

Ein Beweis dieses Theorems besteht darin, das Polygon in Dreiecke mit drei ganzzahligen Ecken und keinen anderen ganzzahligen Punkten zu unterteilen. Man kann dann beweisen, dass jedes unterteilte Dreieck eine exakte Fläche hat . Daher entspricht die Fläche des gesamten Polygons der Hälfte der Anzahl der Dreiecke in der Unterteilung. Nachdem die Fläche auf diese Weise mit der Anzahl der Dreiecke in Beziehung gesetzt wurde, endet der Beweis mit der polyedrischen Formel von Euler , um die Anzahl der Dreiecke auf die Anzahl der Gitterpunkte im Polygon zu beziehen. ${\displaystyle {\tfrac {1}{2}}}$

Der erste Teil dieses Beweises zeigt, dass ein Dreieck mit drei ganzzahligen Ecken und keinen anderen ganzzahligen Punkten die Fläche genau hat , wie es in der Formel von Pick heißt. Der Beweis nutzt die Tatsache, dass alle Dreiecke die Ebene kacheln , wobei benachbarte Dreiecke um ihre gemeinsame Kante um 180° gegeneinander gedreht sind. Bei Kacheln durch ein Dreieck mit drei ganzzahligen Eckpunkten und keinen anderen ganzzahligen Punkten ist jeder Punkt des ganzzahligen Gitters ein Eckpunkt von sechs Kacheln. Da die Anzahl der Dreiecke pro Gitterpunkt (sechs) doppelt so groß ist wie die Anzahl der Gitterpunkte pro Dreieck (drei), sind die Dreiecke in der Ebene doppelt so dicht wie die Gitterpunkte. Jeder skalierte Bereich der Ebene enthält doppelt so viele Dreiecke (im Grenzbereich, wie der Skalierungsfaktor ins Unendliche geht) wie die Anzahl der Gitterpunkte, die er enthält. Daher hat jedes Dreieck die Fläche , wie es für den Beweis benötigt wird. Ein anderer Beweis, dass diese Dreiecke eine Fläche haben, basiert auf der Verwendung des Satzes von Minkowski über Gitterpunkte in symmetrisch-konvexen Mengen. ${\displaystyle {\tfrac {1}{2}}}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle {\tfrac {1}{2}}}$

Dies beweist bereits Picks Formel für ein Polygon, das eines dieser speziellen Dreiecke ist. Jedes andere Polygon kann in spezielle Dreiecke unterteilt werden. Fügen Sie dazu nicht kreuzende Liniensegmente innerhalb des Polygons zwischen Paaren von Gitterpunkten hinzu, bis keine weiteren Liniensegmente mehr hinzugefügt werden können. Die einzigen Polygone, die auf diese Weise nicht in kleinere Formen unterteilt werden können, sind die oben betrachteten speziellen Dreiecke. Daher können in der resultierenden Unterteilung nur spezielle Dreiecke auftreten. Da jedes spezielle Dreieck eine Fläche hat , wird ein Flächenpolygon in spezielle Dreiecke unterteilt. ${\displaystyle {\tfrac {1}{2}}}$${\displaystyle A}$${\displaystyle 2A}$

Die Unterteilung des Polygons in Dreiecke bildet einen ebenen Graphen , und die Eulersche Formel liefert eine Gleichung, die für die Anzahl der Scheitelpunkte, Kanten und Flächen eines ebenen Graphen gilt. Die Scheitelpunkte sind nur die Gitterpunkte des Polygons; es gibt davon. Die Flächen sind die Dreiecke der Unterteilung und der einzelne Bereich der Ebene außerhalb des Polygons. Die Anzahl der Dreiecke ist , also insgesamt gibt es Gesichter. Um die Kanten zu zählen, beachten Sie, dass es in der Unterteilung Seiten von Dreiecken gibt . Jede Kante innerhalb des Polygons ist die Seite von zwei Dreiecken. Es gibt jedoch Kanten von Dreiecken, die entlang der Grenze des Polygons liegen und einen Teil von nur einem Dreieck bilden. Daher gehorcht die Seitenzahl von Dreiecken einer Gleichung, aus der man nach der Kantenzahl auflösen kann, . Setzt man diese Werte für , , und in die Eulersche Formel ein, ergibt sich ${\displaystyle V-E+F=2}$${\displaystyle V=i+b}$${\displaystyle 2A}$${\displaystyle F=2A+1}$${\displaystyle 6A}$${\displaystyle b}$${\displaystyle 6A=2E-b}$${\displaystyle E={\tfrac {6A+b}{2}}}$${\displaystyle V}$${\displaystyle E}$${\displaystyle F}$${\displaystyle V-E+F=2}$

Picks Formel erhält man, indem man diese lineare Gleichung vereinfacht und nach auflöst . Eine alternative Berechnung in gleicher Weise beinhaltet den Beweis, dass die Anzahl der Kanten derselben Unterteilung ist , was zum gleichen Ergebnis führt. ${\displaystyle A}$${\displaystyle E=3i+2b-3}$

Es ist auch möglich, die andere Richtung zu gehen, indem man den Satz von Pick (anders bewiesen) als Grundlage für einen Beweis der Eulerschen Formel verwendet.

Andere Beweise

Alternative Beweise für den Satz von Pick, die die Eulersche Formel nicht verwenden, umfassen Folgendes.

• Man kann das gegebene Polygon rekursiv in Dreiecke zerlegen, so dass einige Dreiecke der Unterteilung eine Fläche größer als 1/2 haben. Sowohl die Fläche als auch die Anzahl der Punkte, die in der Pick-Formel verwendet werden, addieren sich auf die gleiche Weise, so dass die Wahrheit der Pick-Formel für allgemeine Polygone aus ihrer Wahrheit für Dreiecke folgt. Jedes Dreieck unterteilt seinen Begrenzungsrahmen in das Dreieck selbst und zusätzliche rechtwinklige Dreiecke , und die Flächen sowohl des Begrenzungsrahmens als auch der rechtwinkligen Dreiecke sind leicht zu berechnen. Die Kombination dieser Flächenberechnungen ergibt Picks Formel für Dreiecke, und die Kombination von Dreiecken ergibt Picks Formel für beliebige Polygone.
• Das Voronoi-Diagramm des ganzzahligen Gitters unterteilt die Ebene in Quadrate, die um jeden Gitterpunkt zentriert sind. Man kann die Fläche jedes Polygons als Summe seiner Flächen innerhalb jeder Zelle dieses Diagramms berechnen. Für jeden inneren Gitterpunkt des Polygons wird die gesamte Voronoi-Zelle vom Polygon bedeckt. Rasterpunkte an einer Kante des Polygons haben die Hälfte ihrer Voronoi-Zelle bedeckt. Die Voronoi-Zellen von Eckpunkten werden von Beträgen bedeckt, deren Differenzen von einem halben Quadrat (mit einem Argument basierend auf der Umdrehungszahl ) bis zum Korrekturterm in der Formel von Pick summieren.${\displaystyle -1}$
• Anstatt Gitterquadrate zu verwenden, die auf den Gitterpunkten zentriert sind, ist es alternativ möglich, Gitterquadrate zu verwenden, deren Scheitel an den Gitterpunkten liegen. Diese Gitterquadrate schneiden das gegebene Polygon in Stücke, die (durch Angleichen von Quadratpaaren entlang jeder Kante des Polygons) zu einem Polyomino mit der gleichen Fläche neu angeordnet werden können.
• Der Satz von Pick kann auch auf der Grundlage einer komplexen Integration einer doppelt periodischen Funktion in Bezug auf die elliptischen Funktionen von Weierstrass bewiesen werden .
• Die Anwendung der Poisson-Summenformel auf die charakteristische Funktion des Polygons führt zu einem weiteren Beweis.

Picks Theorem wurde in eine Webliste der "Top 100 mathematischen Theoreme" aus dem Jahr 1999 aufgenommen, die später von Freek Wiedijk als Benchmark- Set verwendet wurde, um die Leistungsfähigkeit verschiedener Beweisassistenten zu testen . Ab 2021 war ein Beweis des Pick-Theorems nur in einem der zehn von Wiedijk aufgezeichneten Beweisassistenten formalisiert.

Verallgemeinerungen

Verallgemeinerungen des Satzes von Pick auf nicht-einfache Polygone sind möglich, sind jedoch komplizierter und erfordern mehr Informationen als nur die Anzahl der inneren und Grenzscheitelpunkte. Zum Beispiel hat ein Polygon mit Löchern, die von einfachen ganzzahligen Polygonen begrenzt sind, die voneinander und von der Grenze disjunkt sind, die Fläche ${\displaystyle h}$

Es ist auch möglich, den Satz von Pick auf Regionen zu verallgemeinern, die durch komplexere planare gerade Liniengraphen mit ganzzahligen Scheitelkoordinaten begrenzt sind, unter Verwendung zusätzlicher Terme, die unter Verwendung der Euler-Charakteristik der Region und ihrer Grenze definiert sind, oder auf Polygone mit einem einzigen Grenzpolygon, das selbst unter Verwendung einer Formel, die die Windungszahl des Polygons um jeden ganzzahligen Punkt sowie seine Gesamtwindungszahl einbezieht .

Die Reeve-Tetraeder in drei Dimensionen haben vier ganzzahlige Punkte als Scheitelpunkte und enthalten keine anderen ganzzahligen Punkte. Sie haben jedoch nicht alle das gleiche Volumen. Daher kann es kein Analogon des Satzes von Pick in drei Dimensionen geben, das das Volumen eines Polytops nur als Funktion seiner Anzahl von Innen- und Randpunkten ausdrückt. Diese Volumina können jedoch stattdessen mit Ehrhart-Polynomen ausgedrückt werden .

verwandte Themen

Mehrere andere Themen in der Mathematik beziehen die Flächen von Regionen auf die Anzahl der Gitterpunkte. Unter ihnen besagt der Satz von Blichfeldt , dass jede Form so übersetzt werden kann, dass sie zumindest ihre Fläche in Gitterpunkten enthält. Das Gauss-Kreisproblem betrifft die Begrenzung des Fehlers zwischen den Flächen und der Anzahl von Gitterpunkten in Kreisen. Das Problem, ganzzahlige Punkte in konvexen Polyedern zu zählen, taucht in mehreren Bereichen der Mathematik und Informatik auf. In Anwendungsgebieten ist das Punktplanimeter ein auf Transparenz basierendes Gerät zum Schätzen der Fläche einer Form durch Zählen der darin enthaltenen Rasterpunkte. Die Farey-Folge ist eine geordnete Folge rationaler Zahlen mit beschränkten Nennern, deren Analyse den Satz von Pick beinhaltet.

Eine weitere einfache Methode zur Berechnung der Fläche eines Polygons ist die Schnürsenkelformel . Sie gibt die Fläche eines einfachen Polygons als Summe von Termen an, die aus den Koordinaten aufeinanderfolgender Eckpunktpaare des Polygons berechnet werden. Im Gegensatz zum Theorem von Pick müssen die Scheitelpunkte keine ganzzahligen Koordinaten haben.

Verweise

Externe Links

• Picks Theorem von Ed Pegg, Jr. , das Wolfram Demonstrations Project .
• Pi mit dem Theorem von Pick von Mark Dabbs, GeoGebra