Pick's theorem
In geometry, Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary.
[2] It was popularized in English by Hugo Steinhaus in the 1950 edition of his book Mathematical Snapshots.
[3][4] It has multiple proofs, and can be generalized to formulas for certain kinds of non-simple polygons.
Suppose that a polygon has integer coordinates for all of its vertices.
be the number of integer points interior to the polygon, and let
Therefore, the area of the whole polygon equals half the number of triangles in the subdivision.
is based on the use of Minkowski's theorem on lattice points in symmetric convex sets.
[10] This already proves Pick's formula for a polygon that is one of these special triangles.
Any other polygon can be subdivided into special triangles: add non-crossing line segments within the polygon between pairs of grid points until no more line segments can be added.
[5] The subdivision of the polygon into triangles forms a planar graph, and Euler's formula
gives an equation that applies to the number of vertices, edges, and faces of any planar graph.
The faces are the triangles of the subdivision, and the single region of the plane outside of the polygon.
Each edge interior to the polygon is the side of two triangles.
Therefore, the number of sides of triangles obeys the equation
Pick's formula is obtained by solving this linear equation for
[5] An alternative but similar calculation involves proving that the number of edges of the same subdivision is
[11] It is also possible to go the other direction, using Pick's theorem (proved in a different way) as the basis for a proof of Euler's formula.
[6][12] Alternative proofs of Pick's theorem that do not use Euler's formula include the following.
Pick's theorem was included in a 1999 web listing of the "top 100 mathematical theorems", which later became used by Freek Wiedijk as a benchmark set to test the power of different proof assistants.
As of 2024[update], Pick's theorem had been formalized and proven in only two of the ten proof assistants recorded by Wiedijk.
[17] Generalizations to Pick's theorem to non-simple polygons are more complicated and require more information than just the number of interior and boundary vertices.
It is also possible to generalize Pick's theorem to regions bounded by more complex planar straight-line graphs with integer vertex coordinates, using additional terms defined using the Euler characteristic of the region and its boundary,[18] or to polygons with a single boundary polygon that can cross itself, using a formula involving the winding number of the polygon around each integer point as well as its total winding number.
Therefore, there does not exist an analogue of Pick's theorem in three dimensions that expresses the volume of a polyhedron as a function only of its numbers of interior and boundary points.
[21][22] Several other mathematical topics relate the areas of regions to the numbers of grid points.
Blichfeldt's theorem states that every shape can be translated to contain at least its area in grid points.
[24] The problem of counting integer points in convex polyhedra arises in several areas of mathematics and computer science.
[26] The Farey sequence is an ordered sequence of rational numbers with bounded denominators whose analysis involves Pick's theorem.
[27] Another simple method for calculating the area of a polygon is the shoelace formula.
It gives the area of any simple polygon as a sum of terms computed from the coordinates of consecutive pairs of its vertices.
Unlike Pick's theorem, the shoelace formula does not require the vertices to have integer coordinates.
