PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (23)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very low Entry average rating: No information on entry rating
[parent] proof of Pick's theorem (Proof)

Pick's theorem:

Let $ P\subset\mathbb{R}^2$ be a polygon with all vertices on lattice points on the grid $ \mathbb{Z}^2$. Let $ I$ be the number of lattice points that lie inside $ P$, and let $ O$ be the number of lattice points that lie on the boundary of $ P$. Then the area of $ P$ is

$\displaystyle A(P) = I + \frac{1}{2}O - 1. $
\includegraphics{pick.eps}

To prove, we shall first show that Pick's theorem has an additive character. Suppose our polygon has more than 3 vertices. Then we can divide the polygon $ P$ into 2 polygons $ P_1$ and $ P_2$ such that their interiors do not meet. Both have fewer vertices than $ P.$ We claim that the validity of Pick's theorem for $ P$ is equivalent to the validity of Pick's theorem for $ P_1$ and $ P_2.$

Denote the area, number of interior lattice points and number of boundary lattice points for $ P_k$ by $ A_k, I_k$ and $ O_k,$ respectively, for $ k=1,2.$

Clearly $ A = A_1 + A_2.$

Also, if we denote the number of lattice points on the edges common to $ P_1$ and $ P_2$ by $ L,$ then

$\displaystyle I = I_1 + I_2 + L - 2$
and
$\displaystyle O = O_1 + O_2 -2L + 2$

Hence

$\displaystyle I + \frac{1}{2}O - 1 = I_1 + I_2 + L - 2 + \frac{1}{2}O_1 + \frac{1}{2}O_2 - L + 1 - 1$
$\displaystyle = I_1 + \frac{1}{2}O_1 -1 + I_2 + \frac{1}{2}O_2 -1$

This proves the claim. Therefore we can triangulate $ P$ and it suffices to prove Pick's theorem for triangles. Moreover by further triangulations we may assume that there are no lattice points on the boundary of the triangle other than the vertices. To prove pick's theorem for such triangles, embed them into rectangles.

\includegraphics{pick1.eps}

Again by additivity, it suffices to prove Pick's theorem for rectangles and rectangular triangles which have no lattice points on the hypotenuse and whose other two sides are parallel to the coordinate axes. If these two sides have lengths $ a$ and $ b,$ respectively, we have

$\displaystyle A = \frac{1}{2}ab$
and
$\displaystyle O = a+b+1.$
Furthermore, by thinking of the triangle as half of a rectangle, we get
$\displaystyle I = \frac{1}{2}(a-1)(b-1).$
(Note that here it is essential that no lattice points are on the hypotenuse) From these equations for $ A, I$ and $ O,$ Pick's theorem is satisfied for these triangles.

Finally for a rectangle, whose sides have lengths $ a$ and $ b,$ we find that

$\displaystyle A = ab$
$\displaystyle I = (a-1)(b-1)$
and
$\displaystyle O = 2a + 2b.$
From these Pick's theorem follows for rectangles too. This completes our proof.



"proof of Pick's theorem" is owned by giri.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: proof, equations, lengths, coordinate, parallel, sides, hypotenuse, rectangles, triangulations, triangles, edges, equivalent, meet, interiors, divide, additive, area, boundary, lie on, number, grid, points, lattice, vertices, polygon, Pick's theorem

This is version 2 of proof of Pick's theorem, born on 2002-11-19, modified 2002-11-19.
Object id is 3606, canonical name is ProofOfPicksTheorem.
Accessed 12434 times total.

Classification:
AMS MSC: 51A99 (Geometry :: Linear incidence geometry :: Miscellaneous)
 05B99 (Combinatorics :: Designs and configurations :: Miscellaneous)
 68U05 (Computer science :: Computing methodologies and applications :: Computer graphics; computational geometry)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)