[math-fun] Pick theorems
Pick's theorem (cf. http://en.wikipedia.org/wiki/Pick's_theorem): The area A of a simple polygon with all corners on a square grid is A = i + b/2 - 1 where i is the number of lattice points in the interior and b is the number of lattice points on the boundary. For the following A is the area as number of unit cells covered. Triangular lattice: A = 2*i + b - 2 Hexagonal lattice: A = i/2 + b/4 - 1/2 Square grid, every second column shifted by a half unit: A = i/2 + b/2 - 1 where b counts only the boundary points whose local neighborhood is not concave (i.e., 90 degrees of outside, 270 degrees of inside). I obtained these scribbling on a train ride yesterday. Best, jj P.S.: If anyone can access the following articles, then please email them to me. W. W. Funkenbusch,
From Euler's Formula to Pick's Formula using an Edge Theorem, The American Mathematical Monthly Volume 81 (1974) pages 647-648
Dale E. Varberg, Pick's Theorem Revisited, The American Mathematical Monthly Volume 92 (1985) pages 584-587 Branko Grünbaum and G. C. Shephard, Pick's Theorem, The American Mathematical Monthly Volume 100 (1993) pages 150-161
It appears that at least the "hex lattice" formula is incorrect, grrrr... (so, do not bother). Also I got the papers now. Sorry for the noise, jj * Joerg Arndt <arndt@jjj.de> [Oct 21. 2013 10:49]:
Pick's theorem (cf. http://en.wikipedia.org/wiki/Pick's_theorem): [...]
On Mon, Oct 21, 2013 at 3:52 AM, Joerg Arndt <arndt@jjj.de> wrote:
Pick's theorem (cf. http://en.wikipedia.org/wiki/Pick's_theorem):
Square grid, every second column shifted by a half unit: A = i/2 + b/2 - 1
where b counts only the boundary points whose local neighborhood is not concave (i.e., 90 degrees of outside, 270 degrees of inside).
What about a square of side 2? Doesn't this have i = 1 and b = 4? Andy Latto andy.latto@pobox.com
* Andy Latto <andy.latto@pobox.com> [Oct 22. 2013 08:32]:
On Mon, Oct 21, 2013 at 3:52 AM, Joerg Arndt <arndt@jjj.de> wrote:
Pick's theorem (cf. http://en.wikipedia.org/wiki/Pick's_theorem):
Square grid, every second column shifted by a half unit: A = i/2 + b/2 - 1
where b counts only the boundary points whose local neighborhood is not concave (i.e., 90 degrees of outside, 270 degrees of inside).
What about a square of side 2? Doesn't this have i = 1 and b = 4?
I do not see which configuration you mean. Btw. the formula for the triangular lattice seems to be correct, see Ren Ding, John R.\ Reay: The Boundary Characteristic and Pick's Theorem in the Archimedean Planar Tilings, Journal of Combinatorial Theory, Series A, vol.44, no.1, pp.110-119, (January-1987). http://www.sciencedirect.com/science/article/pii/009731658790063X % "Ren Ding" == "Ding Ren" Ren Ding, Krzysztof Kolodziejczyk, John Reay: A new Pick-type theorem on the hexagonal lattice, Discrete Mathematics, vol.68, no.2-3, pp.171-177, (1988). http://www.sciencedirect.com/science/article/pii/0012365X88901100
Andy Latto andy.latto@pobox.com
[...]
Regards, jj
On Tue, Oct 22, 2013 at 10:29 AM, Joerg Arndt <arndt@jjj.de> wrote:
* Andy Latto <andy.latto@pobox.com> [Oct 22. 2013 08:32]:
On Mon, Oct 21, 2013 at 3:52 AM, Joerg Arndt <arndt@jjj.de> wrote:
Pick's theorem (cf. http://en.wikipedia.org/wiki/Pick's_theorem):
Square grid, every second column shifted by a half unit: A = i/2 + b/2 - 1
where b counts only the boundary points whose local neighborhood is not concave (i.e., 90 degrees of outside, 270 degrees of inside).
What about a square of side 2? Doesn't this have i = 1 and b = 4?
I do not see which configuration you mean.
My numbers were wrong (I was confused as to what lattice you were using), but I think your formula still has a problem. Consider the square with corners at (0,0), (2,0), (0,2) and (2,2). b = 6 (because (0,1) and (2,1) are also on the boundary), and i = 2, because of (1, .5) and (1, 1.5), so your formula gives 3 instead of 4 for the area. I think that any formula that works will need to have the coefficient of i be twice the coefficient of b, so that if it holds for two regions that overlap only on a section of boundary, it will hold for their union. Andy
Here's some interesting info about possible generalizations of Pick's theorem: http://www.ics.uci.edu/~eppstein/junkyard/pick3d.html On Tue, Oct 22, 2013 at 11:49 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Tue, Oct 22, 2013 at 10:29 AM, Joerg Arndt <arndt@jjj.de> wrote:
* Andy Latto <andy.latto@pobox.com> [Oct 22. 2013 08:32]:
On Mon, Oct 21, 2013 at 3:52 AM, Joerg Arndt <arndt@jjj.de> wrote:
Pick's theorem (cf. http://en.wikipedia.org/wiki/Pick's_theorem):
Square grid, every second column shifted by a half unit: A = i/2 + b/2 - 1
where b counts only the boundary points whose local neighborhood is not concave (i.e., 90 degrees of outside, 270 degrees of inside).
What about a square of side 2? Doesn't this have i = 1 and b = 4?
I do not see which configuration you mean.
My numbers were wrong (I was confused as to what lattice you were using), but I think your formula still has a problem. Consider the square with corners at (0,0), (2,0), (0,2) and (2,2). b = 6 (because (0,1) and (2,1) are also on the boundary), and i = 2, because of (1, .5) and (1, 1.5), so your formula gives 3 instead of 4 for the area.
I think that any formula that works will need to have the coefficient of i be twice the coefficient of b, so that if it holds for two regions that overlap only on a section of boundary, it will hold for their union.
Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Andy Latto -
Joerg Arndt -
Victor Miller