皮克定理

皮克定理

給定頂點座標均是整點(或正方形格點)的簡單多邊形皮克定理說明了其面積S和內部格點數目a、邊上格點數目b的關係:S = a + b/2 - 1。

定理提出者

Georg Alexander Pick,1859年生於維也納,1943年死於特萊西恩施塔特集中營

證明

因爲所有簡單多邊形都可切割爲一個三角形和另一個簡單多邊形。考慮一個簡單多邊形P,及跟P有一條共同邊的三角形T。若P符合皮克公式,則只要證明P加上TPT亦符合皮克公式(I),與及三角形符合皮克公式(II),就可根據數學歸納法,對於所有簡單多邊形皮克公式都是成立的。

多邊形

PT的共同邊上有c個格點。

  • P的面積: iP + bP/2 - 1
  • T的面積: iT + bT/2 - 1
  • PT的面積:

(iT + iP + c - 2) + (bT- c + 2 + bP - c + 2 ) /2 - 1
= iPT + bPT/2 - 1

三角形

證明分三部分:證明以下的圖形符合皮克定理:

  1. 所有平行於軸線的矩形;
  2. 以上述矩形的兩條鄰邊和對角線組成的直角三角形;
  3. 所有三角形(因爲它們都可內接於矩形內,將矩形分割成原三角形和至多3個第二點提到的直角三角形)。

矩形

設矩形R長邊短邊各有m,n個格點:

  • AR = (m-1)(n-1)
  • iR = (m-2)(n-2)
  • bR = 2(m+n)-4

iR + bR/2 - 1
= (m-2)(n-2) + (m+n) - 2 - 1
= mn - (m + n) +1
= (m-1)(n-1)

直角三角形

易見兩條鄰邊和對角線組成的兩個直角三角形全等,且i,b相等。設其斜邊上有c個格點。

  • b = m+n+c-3
  • i = ((m-2)(n-2) - c + 2)/2

i + b/2 - 1
= ((m-2)(n-2) - c + 2)/2 + (m+n+c-3)/2 - 1
= (m-2)(n-2)/2 + (m+n - 3)/2
= (m-1)(n-1)/2

推廣

  • 取格點的組成圖形的面積爲一單位。在平行四邊形格點,皮克定理依然成立。套用於任意三角形格點,皮克定理則是A = 2i + b - 2。
  • 對於非簡單的多邊形P,皮克定理A = i + b/2 - χ(P),其中χ(P)表示P的歐拉特徵數。
  • 高維推廣:Ehrhart多項式;一維:植樹問題。
  • 皮克定理和歐拉公式(V-E+F=2)等價

相關日誌