From: Bill Dubuque Newsgroups: k12.ed.math,sci.math Subject: Pick's Theorem: Area of Lattice Polygon [was: Geoboards - Pic's Theorem] Date: Wed, 03 Jun 1998 00:25:19 GMT John Van't Land wrote to k12.ed.math on 31 May 1998: | | When I first started teaching math over 25 years ago, I remember using | geoboards and learning about Pic's Theorem or something like that. | The theorem said that on a geoboard, to find the area of any enclosed | region (it need not be a quadrilateral) you add the number of nails | which the rubber band touches, subtract the number of untouched nails in | the interior, and add one (or something like this--I don't remember the | exact way it was done). | | Does anyone know what I'm trying to describe. Was it Pic's Theorem, | Pik's Theorem, Piques' Theorem...? It's known as Pick's Theorem (G. Pick, 1900; Jbuch 31, 215). I have appended below some references to expository papers. A lattice point is a point with integral coordinates, and a lattice polygon is one whose vertices are lattice points. Pick's Theorem says that the area of a simple lattice polygon P is given by I + B/2 - 1, where I is the number of lattice points in the Interior of P and B is the number of lattice points on the Boundary of P. Pick's Theorem is equivalent to Euler's formula and closely connected to Farey series; it may be generalized to non-simple polygons and to higher dimensions, see the papers cited below. To help remember the correct formula, you can check it on easy cases (unit square, small rectangles, etc) or, better, you can view how it arises from additivity of area. One can view Pick's formula as weighting each interior point by 1, and each boundary point by 1/2, except that two boundary points are omitted. Now suppose we are adjoining two polygons along an edge as in the diagram below. Let's check that Pick's formula gives the same result for the union as it does for the sum of the parts (and thus it gives an additive formula for area, as required). 1/2 1/2 1/2 1/2 ... - @ @ - ... ... - @ @ - ... / \ / \ / \ / \ 0 @ @ 0 @ 0 | | . 1/2 @ @ 1/2 . . @ 1 . . | + | . => . . . 1/2 @ @ 1/2 . . @ 1 . | | 0 @ @ 0 @ 0 \ / \ / \ / \ / ... - @ @ - ... ... - @ @ - ... 1/2 1/2 1/2 1/2 The edge endpoints we choose as the two omitted boundary points. The inside points on the edge were each weighted 1/2 + 1/2 on the left, but are weighted 1 on the right since they become interior. All other points stay interior or stay boundary points, so their weight remains the same on both sides. So Pick's formula is additive. -Bill Dubuque Bruckheimer, Maxim; Arcavi, Abraham. Farey series and Pick's area theorem. Math. Intelligencer 17 (1995), no. 4, 64--67. MR 96h:01019 Grunbaum, Branko; Shephard, G. C. Pick's theorem. Amer. Math. Monthly 100 (1993), no. 2, 150--161. MR 94j:52012 Morelli, Robert. Pick's theorem and the Todd class of a toric variety. Adv. Math. 100 (1993), no. 2, 183--231. MR 94j:14048 Varberg, Dale E. Pick's theorem revisited. Amer. Math. Monthly 92 (1985), no. 8, 584--587. MR 87a:52015 Liu, Andy C. F. Lattice points and Pick's theorem. Math. Mag. 52 (1979), no. 4, 232--235. MR 82d:10042 Haigh, Gordon. A "natural" approach to Pick's theorem. Math. Gaz. 64 (1980), no. 429, 173--180. MR 82b:51001 DeTemple, Duane; Robertson, Jack M. The equivalence of Euler's and Pick's theorems. Math. Teacher 67 (1974), no. 3, 222--226. MR 56 #2854 Gaskell, R. W.; Klamkin, M. S.; Watson, P. Triangulations and Pick's theorem. Math. Mag. 49 (1976), no. 1, 35--37. MR 53 #3881 ---------------------------- message approved for posting by k12.ed.math moderator k12.ed.math is a moderated newsgroup. charter for the newsgroup at www.wenet.net/~cking/sheila/charter.html submissions: post to k12.ed.math or e-mail to k12math@sd28.bc.ca ============================================================================== From: Robin Chapman Newsgroups: k12.ed.math,sci.math Subject: Re: Pick's Theorem: Area of Lattice Polygon [was: Geoboards - Pic's Theorem] Date: Fri, 05 Jun 1998 13:36:45 GMT In article <357b97e5.158500437@news.cyberg8t.com>, Bill Dubuque wrote: [large excerpt of previous article deleted -- djr] Another recent reference is Ricardo Diaz and Sinai Robins Pick's formula via the Weierstrass P-function American Mathematical Monthly 102 431-437 (1995) This is quite a tour de force, relating Pick to the theory of elliptic functions. Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading ---------------------------- message approved for posting by k12.ed.math moderator k12.ed.math is a moderated newsgroup. charter for the newsgroup at www.wenet.net/~cking/sheila/charter.html submissions: post to k12.ed.math or e-mail to k12math@sd28.bc.ca ============================================================================== From: "William L. Bahn" Newsgroups: k12.ed.math,sci.math Subject: Re: Pick's Theorem: Area of Lattice Polygon [was: Geoboards - Pic's Th Date: Thu, 18 Jun 1998 13:07:18 GMT Yes and No. There really isn't "A" relationship between perimeter and area. I can draw lots of polygons that all have the same perimeter and yet have different areas and, conversely, I can draw lots of polygons that all have different perimeters and yet have the same area. What it is based on is that you can take any simple polygon (having lattice point vertices) and break it up into a set of right triangles (some of which may be "negative" area) AND you can further break up those right triangles into smaller right triangles until, eventually, you have a set of right triangles whose hypotenuses (hypoteni?) passes through NO lattice points except at the vertices. So, what is the area of such a triangle: A = bh/2. How many lattice points are on the base line? B = (b+1) How many lattice points are on the height line? H = (h+1), but one of them is also on the base line. How many lattice points are on the hypotentuse? 2, but both are on one of the other two lines. So now write the area in terms of the number of lattice points on the base and height lines: A = (B-1)(H-1)/2 This is O.K., except we have to distinguish between base and height lattice points. How about if we work from the starting point that the more lattice points are in the interior, the larger the area is going to be? So how many lattice point are in the interior of our triangle? Well, the number of points in the interior of a right triangle such as ours is, by symmetry, going to be exactly half of the number of lattice points in the interior of the rectangle having sides b and h. How many is this? Well, inspection should convince you that it is: I = (B-2)(H-2)/2 2I = ((B-1)-1)((H-1)-1) 2I = (B-1)(H-1) - (H-1) - (B-1) + 1 2I = 2A - (H-1) - (B-1) + 1 2I = 2A - (H + B - 3) A = I + (H + B - 3)/2 Now, just like BH was tightly related to the number of interior points, H + B is something that is related to the perimeter points. So, how many points are there total on the perimeter? P = (B) + (H-1) + (2-2) = B + H - 1 Notice that I can now write the area as: A = I + (H + B - 1 -2)/2 A = I + (P - 2)/2 A = I + P/2 - 1 FWIW: I never heard of Pick's Theorem prior to seeing this thread. So all of the above is based on trying to see the underlying fundamentals and then showing that the Theorem follows directly from them. From this point, it is only necessary to show that things work out when you starting combining multiple triangles into more complex polygons. However, notice that if you butt any two of these triangles against each other, the only thing that happens is that a line segment gets removed. The end points of this line segment are points that were perimeter points on both triangles and now they are merely perimeters points on the combined polygon, so the perimeter point count goes down by two as a result. In addition, any other lattice points on this line segment become interior points. In particular notice that for every point that makes this change, you lose two perimeter points (one from each triangle). Therefore, if I have two triangular areas that I butt up against each other I have: A1 = (I1) + (P1)/2 - 1 A2 = (I2) + (P2)/2 - 1 A3 = A1 + A2 = [(I1) + (P1)/2 - 1] + [(I2) + (P2)/2 - 1] If there are N points that become interior points: I3 = (I1 + I2 + N) P3 = (P1 + P2 - 2N - 2) Therefore: A3 = [(I1) + (I2)] + [(P1) + (P2)]/2 - 2 A3 = [(I3) - N] + [(P3) + 2N + 2]/2 - 2 A3 = (I3) - N + (P3)/2 + N + 1 - 2 A3 = (I3) + (P3)/2 - 1 So, by induction, the Theorem works for any polygon that can be represented as the sum of core triangular areas such as we started with. But not all simple polygons can be represented this way. However, we can represent them if we are willing to use additive and subtractive core triangles - the proof that the Theorem remains valid under that extension is left as an exercise for the reader. Jason R. Weiss <346LUEK@cmuvm.csv.cmich.edu> wrote in message <358e8fe1.458779@news.wenet.net>... >Is Pick's formula based on the relationship between perimeter and area? > ---------------------------- message approved for posting by k12.ed.math moderator k12.ed.math is a moderated newsgroup. charter for the newsgroup at www.wenet.net/~cking/sheila/charter.html submissions: post to k12.ed.math or e-mail to k12math@sd28.bc.ca