Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Pick's theorem says that given a square grid (that is, all points in the plane with integer coordinates) and a polygon without holes and non selt-intersecting whose vertices are grid points, its area is given by

i + b/2 - 1

where i is the number of interior lattice points and b is the number of points on its boundary. Theorem and proof may be found on Wikipedia.

Let us suppose that the grid is not square but triangular (or hexagonal). Does a similar theorem hold?

share|improve this question
3  
That is crazy, why have I not heard of this –  BlueRaja - Danny Pflughoeft Jul 27 '10 at 8:14
    
I found it for the first time in Gardner's Sixth Book of Mathematical Diversions. But it's not a topic explained at school, unfortunately. –  mau Jul 27 '10 at 8:22
    
Interesting question, for sure. Will have to think about it a bit! –  Noldorin Jul 27 '10 at 8:44
    
RE: It's not a topic explained at school. I have seen it in several geometry textbooks, but unfortunately it isn't in the "core curriculum" (it isn't necessary to go on to other things) so it is done purely at the teacher discretion. –  Jason Dyer Jul 30 '10 at 16:36
add comment

5 Answers

up vote 12 down vote accepted

The short answer is that, no, there can be no formula for polygons with vertices in the hexagonal lattice in terms of just boundary and interior points. This is based on the fact that primitive triangles on this lattice--ones with no lattice points on their boundary (besides the vertices) or in the interior--can have different areas, whereas for the square lattice all primitive triangles have area 1/2.

However, as Casebash has partly gotten at in his answer, you can approximate things well if you compute what, in the below paper, is called the "boundary characteristic" of the polygon, a number that is somewhat complicated to think to compute, but which gives a decent proxy for how many of each type of primitive triangle the polygon contains.

Kolodziejczyk has been the main one doing work on hexagonal lattice results of this type that I know; he's worth looking up for similar results. Ding Ren is another, and the older work of Grunbaum, etc., still bears on the problem.

"A Fast Pick-Type Approximation for the Area of H-Polygons," Ren, Kolodziejczyk, et al., American Mathematical Monthly, 1993.

Available at JSTOR if you have access.

share|improve this answer
add comment

This is a very interesting question. I don't have a complete solution yet, but I did get some results. Consider an arbitrary distribution of points. Let P(i,b)=i+b/2-1 where i is the number of internal points and P is the number of boundary points. Let P(A)=P(i_A,b_A), where A is a simple polygon with all its vertices on the points. Wikipedia shows that P(C)=P(A)+P(T) where T is a triangle that shares a single edge with A and C a simple polygon formed by the union of A and T. Since all simple polygons can be triangulated, P(C)=sum P(t) for all t in the triangulation of C.

The proof then has a second part that shows P(t) equals the area for any triangle. So if we want to generalise it for other grids, we have to find a property equal to P(T) for any triangle.

share|improve this answer
    
Oh, it must also satisfy P(C)=P(A)+P(B) for all shapes A and B –  Casebash Jul 27 '10 at 9:24
add comment

(For an integer λ and a lattice polygon P) denote by λP polygon P stretched by λ times. Then number N(λP) of points inside the polygon λ is a quadratic polynomial in λ with leading coefficient S(P). This is the form of Pick's theorem that holds for any lattice (and obvious analogue works in any dimension — unlike usual Pick's formula that has no analogue in 3d even for the cubic lattice).

For the square lattice it yields ordinary Pick's theorem since for a parallelogram P on the square lattice $N(\lambda P)\approx\lambda^2(i+\frac{b}{2}-1)S(P)$ as λ→∞ and general theorem follows from the theorem for parallelograms by additivity.

share|improve this answer
add comment

A downloadable Word document called Pick A Shape, at http://www.1000problems.org/ claims that if the units are measured in triangles instead of squares, the formula is A=2i+b-1

share|improve this answer
    
The formula is actually A=2i+b-2, and it works for any triangular lattice, not just equilateral. A=1 for each triangle in the lattice. –  Rick Walcott Apr 19 '12 at 19:26
add comment

Find the area of the polygon on the triangular grid in the usual way using Pick's formula, but multiply by $\sqrt{3}$ and divide by 2. This works because each square can be mapped to a parallelogram comprised of two equilateral triangles, and the area of the parallelogram is $\frac{\sqrt{3}}{2}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.