Picks sætning

Picks sætning er en formel, der beregner arealet af et simpelt polygon indtegnet i et gitter hvis hjørner ligger på punkter med heltalskoordinater. Formlen lyder $$A=I+\frac{B}{2}-1$$ hvor $A$ er arealet af polygonen, $I$ er antallet af gitterpunkter inden i polygonen og $B$ er antallet af gitterpunkter på dens kant.

Bemærk at Picks sætning kun gælder for simple polygoner. Dvs. polygonen ikke må have huller i sig, og siderne må ikke krydse hinanden.

I polygonen foroven er $I=13$ og $B=4$. Dermed bliver arealet lig med $A=13+\frac{4}{2}-1=14$.

Bevis

Vi viser først, at Picks sætning holder for rektangler, hvis sider er parallelle med gitteret. Antag at rektanglet har højden $h$ enheder og bredden $b$ enheder. Rektanglet må nødvendigvis indeholder $$I=(h-1)\cdot (b-1)$$ gitterpunkter. Desuden må kantern af rektanglet indeholde $$B=2h+2b$$ gitterpunkter. Dermed er \begin{align*} I+\frac{B}{2}-1 &= (h-1)\cdot (b-1) + \frac{2b+2h}{2}-1 \\ &= h\cdot b-h-b+1+(b+h)-1 \\ &= h\cdot b \end{align*} som stemmer overens med arealet af rektanglet.

Vi viser herefter, at formlen holder for retvinklede trekanter, hvis kateter er parallelle med gitteret. Lad $B$ og $I$ angive hhv. kant og indre gitterpunkter for rektanglet. Hvis $B_k$ angiver antallet af gitterpunkter på de to kateter og $B_h$ angiver antallet af gitterpunkter på hypotenusen, må der gælder at $$B=B_k+B_h$$ Bemærk, at vi kan danne et rektangel med sidelængder svarende til katetelængderne i trekanten. Vi ved at arealet af rektanglet opfylder Picks sætning og er $$A_r=I_r+\frac{B_r}{2}-1$$ Antallet af gitterpunkter på kanten af rektanglet, må være det dobbelte af gitterpunkter på de to kateter, minus de to hjørnepunkter, som vi tæller dobbelt. Dvs. $$B_r=2\cdot B_k-2$$ Antallet af indre gitterpunkter i rektangle må være det dobbelt af indre gitterpunkter i trekanten, minus antallet af gitterpunkter beliggende på hypotenusen. Dvs. $$I_r=2\cdot I+B_h$$ Arealet af rektanglet er dobbelt så stort som arealet af trekanten, og dermed er arealet af trekanten lig med \begin{align*} A &= \frac{1}{2}\cdot A_r \\ &= \frac{1}{2}\cdot\left(I_r+\frac{B_r}{2}-1\right) \\ &= \frac{1}{2}\cdot\left(2\cdot I+B_h+\frac{2\cdot B_k-2}{2}-1\right) \\ &= \frac{1}{2}\cdot\left(2\cdot I+B_h+B_k-2\right) \\ &= I+\frac{B}{2}-1 \end{align*} Vi viser herefter at formlen holder for vilkårlige trekanter. Lad $B$ og $I$ angive hhv. kant og indre gitterpunkter for den vilkårlige trekant. Først danner vi det omskrevne rektangel til den vilkårlige trekant. Det omskrevne rektangel vil bestå af den vilkårlige trekant samt 3 retvinklede trekanter. Lad $B_r$ angive gitterpunkter på kanten af rektanglet og $B_1, B_2, B_3$ angive gitterpunkter på kanterne af hhv. de tre retvinklede trekanter. Der må nøvendigvis gælde at $$B_1+B_2+B_3=B+B_r$$ Lad $I_r$ angive indre gitterpunkter i rektanglet og $B_1, B_2, B_3$ angive indre gitterpunkter for hhv. de tre retvinklede trekanter. For de indre punkter må der gælde at $$I_1+I_2+I_3+(B-3)+I=I_r$$ Vi ved at Picks sætning holder for rektanglet og alle de retvinklede trekanter. Om arealet gælder der dermed at \begin{align*} A &= A_r - A_1 - A_2 - A_3 \\ &= \left(I_r+\frac{B_r}{2}-1\right) - \left(I_1+\frac{B_1}{2}-1\right) - \left(I_2+\frac{B_2}{2}-1\right) - \left(I_3+\frac{B_3}{2}-1\right) \\ &= 2 + (I_r - I_1 - I_2 - I_3) + \frac{B_r - B_1 - B_2 - B_3 - 3}{2} \\ &= 2 + (B-3+I) + \frac{B_r + B - 3}{2} \\ &= I+\frac{B}{2}-1 \end{align*} Vi viser endelig at hvis Picks sætning holder for to vilkårlige simple polygoner, så kan vi sætte dem sammen til et nyt polygon, hvor Picks sætning også holder. Lad $B$ og $I$ angive hhv. kant og indre gitterpunkter for det nye polygon. Lad $I_1, I_2$ angive indre gitterpunkter for hhv. de to polygoner. Når vi sætter de to polygoner sammen, vil de overlappe i en linje. Lad antallet af gitterpunkter på denne linje være angivet med $L$. Der må nødvendigvis gælde at $$I=I_1+I_2+L$$ Lad $I_1, I_2$ angive gitterpunkter på kanterne for hhv. de to polygoner. Her må der gælde at $$B_1+B_2=B+2\cdot L+2$$ Vi ved at Picks sætning holder for de to vilkårlige polygoner. Om arealet af det sammensatte polygon gælder der dermed at \begin{align*} A &= A_1+A_2 \\ &= \left(I_1+\frac{B_1}{2}-1\right) + \left(I_2+\frac{B_2}{2}-1\right) \\ &= I_1 + I_2 + L + \frac{B_1+B_2-L}{2} - 2 \\ &= I + \frac{B + 2}{2}-2 \\ &= I+\frac{B}{2}-1 \end{align*} Da ethvert polygon kan opdeles i et vilkårlige antal vilkårlige trekanter, kan vi dermed konkludere at Picks sætning må gælde for alle simple polygoner.