Pick's theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
i = 7, b = 8, A = i + b/2 − 1 = 10

In geometry, Pick's theorem provides a formula for the area of a polygon with integer vertex coordinates in terms of the number of integer points it contains and on its boundary. The result was first described by Georg Alexander Pick in 1899,[1] and popularized in English by Hugo Steinhaus in the 1950 edition of his book Mathematical Snapshots.[2][3]

Formula[edit]

Suppose that a polygon has integer coordinates for all of its vertices, let be the number of integer points that are interior to the polygon and let be the number of integer points on its boundary (including both vertices and points along the sides of the polygon). Then the area of this polygon is:[4][5][6][7]

The example shown has interior points and boundary points, so its area is square units.

Proofs[edit]

Via Euler's formula[edit]

One proof of this theorem uses Euler's polyhedral formula to reduce the problem to the case of a triangle with three integer vertices and no other integer points. Such a triangle can tile the plane by copies of itself, rotated by 180° around the midpoint of each edge. The triangles of this tiling are twice as dense as the integer points (each integer point belongs to six triangles, while each triangle touches only three integer points) from which it follows that their area is exactly , as Pick's theorem (once it has been proved) would also imply.[4] It is also possible to use Minkowski's theorem on lattice points in symmetric convex sets to prove that these triangles have area .[8]

Any other simple polygon can be subdivided into triangles of this type. If the polygon has interior integer points, boundary points, and area , then we can use these numbers of points to count the vertices, faces, and edges of the subdivision, used by Euler's formula. The interior and boundary points are the vertices of the subdivision, so there are total vertices. The subdivision has faces: triangles of area to cover the area of the polygon, and one more face outside the polygon. Finally, each edge of the subdivision forms the side of one or two triangles. There are sides of triangles, and edges of the subdivision that only form the side of one triangle rather than two, so the total number of edges in the subdivision is . Plugging these numbers into Euler's formula gives

and Pick's formula can be obtained by simplifying this linear equation and solving for .[4] Alternatively, the number of edges can be calculated as , leading to the same result.[9]

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.[5][10]

Other proofs[edit]

Alternative proofs of Pick's theorem that do not use Euler's formula include

  • a proof based on the recursive decomposition of the given polygon into larger triangles, the additivity of both area counts and point counts under this decomposition, and a formula for the area of a triangle based on the subdivision of its bounding box into the given triangle and additional right triangles,[6][7][11]
  • a proof based on summing up the areas covered by the polygon within each cell of a Voronoi diagram of the points of the integer grid (a unit square with each grid point at the center), observing that interior points have their entire cell covered, edge points have half their square covered, and the corner points are covered by amounts whose differences from half a square (using an argument based on turning number) total to the correction term in Pick's formula,[7]
  • a dissection-based proof in which the given polygon is cut into pieces by the boundaries of the integer grid squares, and those pieces are rearranged (by matching up pairs of squares along each edge of the polygon) into a polyomino with the same area,[12]
  • a proof based on complex integration of a doubly periodic function related to Weierstrass's elliptic functions,[13] and
  • a proof obtained by applying the Poisson summation formula to the characteristic function of the polygon.[14]

Generalizations[edit]

Generalizations to Pick's theorem to non-simple polygons are possible, but are more complicated and require more information than just the number of interior and boundary vertices.[2]

The Reeve tetrahedra are a family of tetrahedra in three dimensions with integer points as vertices and no interior integer points. Because they have varying volumes, there can be no analogue of Pick's theorem in three dimensions that expresses the volume of a polytope as a function only of its numbers of interior and boundary points.[15] However, these volumes can instead be expressed using Ehrhart polynomials.[16][17]

See also[edit]

References[edit]

  1. ^ Pick, Georg (1899). "Geometrisches zur Zahlenlehre". Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen "Lotos" in Prag. (Neue Folge). 19: 311–319. JFM 33.0216.01. CiteBank:47270
  2. ^ a b Grünbaum, Branko; Shephard, G. C. (February 1993). "Pick's theorem". The American Mathematical Monthly. 100 (2): 150–161. doi:10.2307/2323771. JSTOR 2323771.
  3. ^ Steinhaus, H. (1950). Mathematical Snapshots. Oxford University Press. p. 76. MR 0036005.
  4. ^ a b c Aigner, Martin; Ziegler, Günter M. (2018). "Three applications of Euler's formula: Pick's theorem". Proofs from THE BOOK (6th ed.). Springer. pp. 93–94. doi:10.1007/978-3-662-57265-8. ISBN 978-3-662-57265-8.
  5. ^ a b Wells, David (1991). "Pick's theorem". The Penguin Dictionary of Curious and Interesting Geometry. Penguin Books. pp. 183–184.
  6. ^ a b Beck, Matthias; Robins, Sinai (2015). "2.6 Pick's theorem". Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics (2nd ed.). Springer. pp. 40–43. doi:10.1007/978-1-4939-2969-6. ISBN 978-1-4939-2968-9. MR 3410115.
  7. ^ a b c Ball, Keith (2003). "Chapter 2: Counting Dots". Strange Curves, Counting Rabbits, and Other Mathematical Explorations. Princeton University Press, Princeton, NJ. pp. 25–40. ISBN 0-691-11321-1. MR 2015451.
  8. ^ Ram Murty, M.; Thain, Nithum (2007). "Pick's theorem via Minkowski's theorem". The American Mathematical Monthly. 114 (8): 732–736. doi:10.1080/00029890.2007.11920465. JSTOR 27642309. MR 2354443.
  9. ^ Funkenbusch, W. W. (June–July 1974). "From Euler's formula to Pick's formula using an edge theorem". Classroom Notes. The American Mathematical Monthly. 81 (6): 647–648. doi:10.2307/2319224. JSTOR 2319224. MR 1537447.
  10. ^ DeTemple, Duane; Robertson, Jack M. (March 1974). "The equivalence of Euler's and Pick's theorems". The Mathematics Teacher. 67 (3): 222–226. doi:10.5951/mt.67.3.0222. JSTOR 27959631.
  11. ^ Varberg, Dale E. (1985). "Pick's theorem revisited". The American Mathematical Monthly. 92 (8): 584–587. doi:10.2307/2323172. JSTOR 2323172. MR 0812105.
  12. ^ Trainin, J. (November 2007). "An elementary proof of Pick's theorem". The Mathematical Gazette. 91 (522): 536–540. doi:10.1017/S0025557200182270. JSTOR 40378436.
  13. ^ Diaz, Ricardo; Robins, Sinai (1995). "Pick's formula via the Weierstrass -function". The American Mathematical Monthly. 102 (5): 431–437. doi:10.2307/2975035. JSTOR 2975035. MR 1327788.
  14. ^ Brandolini, L.; Colzani, L.; Robins, S.; Travaglini, G. (2021). "Pick's theorem and convergence of multiple Fourier series". The American Mathematical Monthly. 128 (1): 41–49. doi:10.1080/00029890.2021.1839241. MR 4200451.
  15. ^ Reeve, J. E. (1957). "On the volume of lattice polyhedra". Proceedings of the London Mathematical Society. Third Series. 7: 378–395. doi:10.1112/plms/s3-7.1.378. MR 0095452.
  16. ^ Beck & Robins (2015), 3.6 "From the discrete to the continuous volume of a polytope", pp. 76–77
  17. ^ Diaz, Ricardo; Robins, Sinai (1997). "The Ehrhart polynomial of a lattice polytope". Annals of Mathematics. Second Series. 145 (3): 503–518. doi:10.2307/2951842. MR 1454701.

External links[edit]