2019-05-02 is Holocaust Memorial Day in Israel. I’d like to mention the work of an Austrian-Czech mathematician – Georg Pick – whom the Nazis murdered in Terezin. Like many great mathematicians in the second half of the 19th century and beginning of the 20th century, Pick worked on a great many subjects. But he is perhaps most well-known for his work on complex analysis and geometry (and what would later become topology) on continuous manifolds. In many ways his mathematical career was part of the bridge between the concepts of these centuries.
Pick had retired from his academic career in 1927 and lived in Vienna. He did not leave in time after the Anschluss, and was deported to Terezin in 1942. He died shortly after, aged 82. A short biography of his life is available.
One of his most important works is the Nevanlinna-Pick Interpolation Theorem gives necessary and sufficient conditions for the existence of a holomorphic (“nice”) function from the unit disk to itself that solves n equations for its values on particular points of the disk. The field discovered by Pick and by Nevanlinna (independently of each other) continued throughout the 20th century.
His most famous work, however, is the amazing Pick’s Theorem. You may have been asked to prove it in a Discrete Mathematics class; indeed it is accessible to high-school students.
Suppose P is a polygon with no holes, and all corners located on points of a grid. The area of P is I + E/2 - 1, where I is the number of points of the grid inside the polygon and E is the number of points of the grid on the boundary of the polygon.
This example from Wikipedia has I=7 and E=8, giving an area of 10. You can verify the area of the shape by splitting it up into triangles.
The proof is actually quite simple, provided you don’t dig too deeply into what “no holes” means. This is my take on it, optimized for simplicity and speed (rather than precision and economy). Call a polygon with all corners on points of a grid a “grid polygon”.
This is the basic tool.
Suppose you have 2 grid polygons with a common edge, and suppose each of them satisfies the theorem. So the first has area I₁ + E₁/2 - 1, and the second has area I₂ + E₂/2 - 1.
Suppose also that the common edge has n grid points on it. How many interior points does the joined polygon have? I₁ + I₂ + n - 2, because each point interior to one of the polygons remains interior, and all n points of the common edge become interior except for the 2 corners.
Similarly, the joined polygon has E₁ + E₂ - 2n + 2 exterior grid points, because:
- Each of the exterior points on just one of the polygons remains – there are E₁ - n on the first and E₂ - n on the second;
- Each of the n-2 exterior points apart from the 2 ends on the shared line becomes interior (and is no longer exterior); The 2 ends of the shared line remain.
So Pick’s formula for the joined polygon is I + E/2 - 1 = I₁ + I₂ + (n-2) + (E₁ + E₂ - 2n + 2)/2 - 1 = I₁ + E₁/2 + I₂ + E₂/2 + n - 2 - n + 1 - 1 = I₁ + E₁/2 + I₂ + E₂/2 - 2 Which is exactly the sum of the areas of the 2 polygons.
Pick’s method is to use this joining trick over and over again, to prove the theorem! The details are tedious (but are where the “no holes” comes from), skip to “Holes” when you run out of patience.
These are easy enough, just count up the numbers and it works.
For a right triangle, if the hypotenuse has no grid points except at its 2 corners, we can count areas and see that Pick’s formula holds. OR, we can glue 2 such triangles into a rectangle. The formula holds for the rectangle, so it holds for each of the constituent triangles… and both have the same E and I, so the formula has to hold.
If the hypotenuse does have >2 grid points, use them to split it up into lots and lots of smaller triangles which don’t. By joining, it holds for any right triangle.
The joining trick does some more work.
Say we have a polygon whose convex hull is not a triangle. Put it inside its bounding box. Now each of the extra bits (1, 2, 3, 4 in the diagram) has a smaller bounding box, so we can use induction to prove Pick’s theorem for it. The theorem also holds for the bounding box – it’s a rectangle – so by joining the bits and the polygon we can get Pick’s theorem for the polygon.
If the convex hull is a triangle we need to do some more work (because the leftover bits from the bounding box can have the same bounding box):
- Pad the triangle into its bounding box. It will have 3 leftover bits, each a right triangle. That proves Pick’s theorems for the triangle.
- Use the leftover bits from the polygon inside the its triangular convex hull. Each of these has a smaller bounding box, and joining works.
(Actually Pick did not do it this way, because he knew more geometry and could prove that every polygon has an interior diagonal. But that’s actually more effort than I’m willing to make, so instead we just used joining one extra time…)
The theorem doesn’t hold when the polygon has holes! You can remove the inner polygons that have holes, and end up with A = I + E/2 - 1 + n… but then you need to start going into holes within the holes and other complications. Betti numbers make an appearance, and you end up with an equivalence between Pick’s Theorem and Euler’s Theorem with holes (which connects the number of vertices and edges of a polygon with holes). On the plus side, if you know A, I and E, plugging them in gives the number of holes n.