Movatterモバイル変換

[0]ホーム

Jump to content

Pick's theorem

Edit links

This is a good article. Click here for more information.

From Wikipedia, the free encyclopedia

Formula for area of a grid polygon

For the theorem in complex analysis, seeSchwarz lemma § Schwarz–Pick theorem.

Farey sunburst of order 6, with 1 interior(red) and 96 boundary(green) points giving an area of1 +⁠96/2⁠ − 1 = 48^[1]

Ingeometry,Pick's theorem provides a formula for thearea of asimple polygon with integervertex coordinates, in terms of the number of integer points within it and on its boundary. The result was first described byGeorg Alexander Pick in 1899.^[2] It was popularized in English byHugo Steinhaus in the 1950 edition of his bookMathematical Snapshots.^[3]^[4] It has multiple proofs, and can be generalized to formulas for certain kinds of non-simple polygons.

Formula

[edit]

Suppose that a polygon hasinteger coordinates for all of its vertices. Let $i {\displaystyle i}$ be the number of integer points interior to the polygon, and let $b {\displaystyle b}$ be the number of integer points on its boundary (including both vertices and points along the sides). Then thearea $A {\displaystyle A}$ of this polygon is:^[5]^[6]^[7]^[8] $A=i+{\frac {b}{2}}-1.$ The example shown has $i=7$ interior points and $b=8$ boundary points, so its area is $A=7+{\tfrac {8}{2}}-1=10$ square units.

Proofs

[edit]

Via Euler's formula

[edit]

One proof of this theorem involves subdividing the polygon into triangles with three integer vertices and no other integer points. One can then prove that each subdivided triangle has area exactly ${\tfrac {1}{2}}$ . Therefore, the area of the whole polygon equals half the number of triangles in the subdivision. After relating area to the number of triangles in this way, the proof concludes by usingEuler's polyhedral formula to relate the number of triangles to the number of grid points in the polygon.^[5]

Tiling of the plane by copies of a triangle with three integer vertices and no other integer points, as used in the proof of Pick's theorem

The first part of this proof shows that a triangle with three integer vertices and no other integer points has area exactly ${\tfrac {1}{2}}$ , as Pick's formula states. The proof uses the fact that all trianglestile the plane, with adjacent triangles rotated by 180° from each other around their shared edge.^[9] For tilings by a triangle with three integer vertices and no other integer points, each point of the integer grid is a vertex of six tiles. Because the number of triangles per grid point (six) is twice the number of grid points per triangle (three), the triangles are twice as dense in the plane as the grid points. Any scaled region of the plane contains twice as many triangles (in the limit as the scale factor goes to infinity) as the number of grid points it contains. Therefore, each triangle has area ${\tfrac {1}{2}}$ , as needed for the proof.^[5] A different proof that these triangles have area ${\tfrac {1}{2}}$ is based on the use ofMinkowski's theorem on lattice points in symmetric convex sets.^[10]

Subdivision of a grid polygon into special triangles

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. The only polygons that cannot be subdivided in this way are the special triangles considered above; therefore, only special triangles can appear in the resulting subdivision. Because each special triangle has area ${\tfrac {1}{2}}$ , a polygon of area $A {\displaystyle A}$ will be subdivided into $2A$ special triangles.^[5]

The subdivision of the polygon into triangles forms aplanar graph, and Euler's formula $V-E+F=2$ gives an equation that applies to the number of vertices, edges, and faces of any planar graph. The vertices are just the grid points of the polygon; there are $V=i+b$ of them. The faces are the triangles of the subdivision, and the single region of the plane outside of the polygon. The number of triangles is $2A$ , so altogether there are $F=2A+1$ faces. To count the edges, observe that there are $6A$ sides of triangles in the subdivision. Each edge interior to the polygon is the side of two triangles. However, there are $b {\displaystyle b}$ edges of triangles that lie along the polygon's boundary and form part of only one triangle. Therefore, the number of sides of triangles obeys the equation $6A=2E-b$ , from which one can solve for the number of edges, $E={\tfrac {6A+b}{2}}$ . Plugging these values for $V {\displaystyle V}$ , $E {\displaystyle E}$ , and $F {\displaystyle F}$ into Euler's formula $V-E+F=2$ gives $(i+b)-{\frac {6A+b}{2}}+(2A+1)=2.$ Pick's formula is obtained by solving thislinear equation for $A {\displaystyle A}$ .^[5] An alternative but similar calculation involves proving that the number of edges of the same subdivision is $E=3i+2b-3$ , leading to the same result.^[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]

Other proofs

[edit]

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

One can recursively decompose the given polygon into triangles, allowing some triangles of the subdivision to have area larger than 1/2. Both the area and the counts of points used in Pick's formula add together in the same way as each other, so the truth of Pick's formula for general polygons follows from its truth for triangles. Any triangle subdivides itsbounding box into the triangle itself and additionalright triangles, and the areas of both the bounding box and the right triangles are easy to compute. Combining these area computations gives Pick's formula for triangles, and combining triangles gives Pick's formula for arbitrary polygons.^[7]^[8]^[13]
Alternatively, instead of using grid squares centered on the grid points, it is possible to use grid squares having their vertices at the grid points. These grid squares cut the given polygon into pieces, which can be rearranged (by matching up pairs of squares along each edge of the polygon) into apolyomino with the same area.^[14]
Pick's theorem may also be proved based oncomplex integration of adoubly periodic function related toWeierstrass elliptic functions.^[15]
Applying thePoisson summation formula to thecharacteristic function of the polygon leads to another proof.^[16]

Pick's theorem was included in a 1999 web listing of the "top 100 mathematical theorems", which later became used by Freek Wiedijk as abenchmark set to test the power of differentproof 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

[edit]

i = 2,b = 12,h = 1,A =i +⁠b/2⁠ +h − 1 = 8

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.^[3]^[18] For instance, apolygon withh holes bounded by simple integer polygons, disjoint from each other and from the boundary, has area^[19] $A=i+{\frac {b}{2}}+h-1.$ It is also possible to generalize Pick's theorem to regions bounded by more complexplanar straight-line graphs with integer vertex coordinates, using additional terms defined using theEuler characteristic of the region and its boundary,^[18] or to polygons with a single boundary polygon that can cross itself, using a formula involving thewinding number of the polygon around each integer point as well as its total winding number.^[3]

Reeve tetrahedra showing that Pick's theorem does not apply in higher dimensions

TheReeve tetrahedra in three dimensions have four integer points as vertices and contain no other integer points, but do not all have the same volume. 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.^[20] However, these volumes can instead be expressed usingEhrhart polynomials.^[21]^[22]

References

[edit]

^Kiradjiev, Kristian (October 2018)."Connecting the dots with Pick's theorem"(PDF).Mathematics Today. pp. 212–214.
^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
^^a ^b ^cGrünbaum, Branko;Shephard, G. C. (February 1993). "Pick's theorem".The American Mathematical Monthly.100 (2):150–161.doi:10.2307/2323771.JSTOR 2323771.MR 1212401.
^Steinhaus, H. (1950).Mathematical Snapshots. Oxford University Press. p. 76.MR 0036005.
^^a ^b ^c ^d ^eAigner, 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.
^^a ^bWells, David (1991). "Pick's theorem".The Penguin Dictionary of Curious and Interesting Geometry. Penguin Books. pp. 183–184.
^^a ^bBeck, 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.
^^a ^bBall, 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.
^Martin, George Edward (1982).Transformation geometry. Undergraduate Texts in Mathematics. Springer-Verlag. Theorem 12.1, page 120.doi:10.1007/978-1-4612-5680-9.ISBN 0-387-90636-3.MR 0718119.
^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.S2CID 38855683.
^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.
^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.MR 0444503.
^Varberg, Dale E. (1985). "Pick's theorem revisited".The American Mathematical Monthly.92 (8):584–587.doi:10.2307/2323172.JSTOR 2323172.MR 0812105.
^Trainin, J. (November 2007). "An elementary proof of Pick's theorem".The Mathematical Gazette.91 (522):536–540.doi:10.1017/S0025557200182270.JSTOR 40378436.S2CID 124831432.
^Diaz, Ricardo; Robins, Sinai (1995). "Pick's formula via the Weierstrass $\wp$ -function".The American Mathematical Monthly.102 (5):431–437.doi:10.2307/2975035.JSTOR 2975035.MR 1327788.
^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.S2CID 231624428.
^Wiedijk, Freek."Formalizing 100 Theorems". Radboud University Institute for Computing and Information Sciences. Retrieved2024-02-20.
^^a ^bRosenholtz, Ira (1979). "Calculating surface areas from a blueprint".Mathematics Magazine.52 (4):252–256.doi:10.1080/0025570X.1979.11976797.JSTOR 2689425.MR 1572312.
^Sankar, P. V.; Krishnamurthy, E. V. (August 1978). "On the compactness of subsets of digital pictures".Computer Graphics and Image Processing.8 (1):136–143.doi:10.1016/s0146-664x(78)80021-5.
^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.
^Beck & Robins (2015), 3.6 "From the discrete to the continuous volume of a polytope", pp. 76–77
^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.JSTOR 2951842.MR 1454701.
^Olds, C. D.;Lax, Anneli;Davidoff, Giuliana P. (2000). "Chapter 9: A new principle in the geometry of numbers".The Geometry of Numbers. Anneli Lax New Mathematical Library. Vol. 41. Mathematical Association of America, Washington, DC. pp. 119–127.ISBN 0-88385-643-3.MR 1817689.
^Guy, Richard K. (2004). "F1: Gauß's lattice point problem".Unsolved Problems in Number Theory. Problem Books in Mathematics. Vol. 1 (3rd ed.). New York: Springer-Verlag. pp. 365–367.doi:10.1007/978-0-387-26677-0.ISBN 0-387-20860-7.MR 2076335.
^Barvinok, Alexander (2008).Integer Points In Polyhedra. Zurich Lectures in Advanced Mathematics. Vol. 11. Zürich: European Mathematical Society.doi:10.4171/052.ISBN 978-3-03719-052-4.MR 2455889.
^Bellhouse, D. R. (1981). "Area estimation by point-counting techniques".Biometrics.37 (2):303–312.doi:10.2307/2530419.JSTOR 2530419.MR 0673040.
^Bruckheimer, Maxim; Arcavi, Abraham (1995). "Farey series and Pick's area theorem".The Mathematical Intelligencer.17 (4):64–67.doi:10.1007/BF03024792.MR 1365013.S2CID 55051527.
^Braden, Bart (1986)."The surveyor's area formula"(PDF).The College Mathematics Journal.17 (4):326–337.doi:10.2307/2686282.JSTOR 2686282. Archived fromthe original(PDF) on 2015-04-06. Retrieved2021-07-04.