給定頂點(diǎn)座標(biāo)均是整點(diǎn)(或正方形格點(diǎn))的簡(jiǎn)單多邊形,皮克定理說明了其面積A和內(nèi)部格點(diǎn)數(shù)目i、邊上格點(diǎn)數(shù)目b的關(guān)系:A = i + b/2 - 1。
證明
因?yàn)樗泻?jiǎn)單多邊形都可切割為一個(gè)三角形和另一個(gè)簡(jiǎn)單多邊形。考慮一個(gè)簡(jiǎn)單多邊形P,及跟P有一條共同邊的三角形T。若P符合皮克公式,則只要證明P加上T的PT亦符合皮克公式(I),與及三角形符合皮克公式(II),就可根據(jù)數(shù)學(xué)歸納法,對(duì)于所有簡(jiǎn)單多邊形皮克公式都是成立的。
多邊形
設(shè)P和T的共同邊上有c個(gè)格點(diǎn)。
- 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
三角形
證明分三部分:證明以下的圖形符合皮克定理:
- 所有平行于軸線的矩形;
- 以上述矩形的兩條鄰邊和對(duì)角線組成的直角三角形;
- 所有三角形(因?yàn)樗鼈兌伎蓛?nèi)接于矩形內(nèi),將矩形分割成原三角形和至多3個(gè)第二點(diǎn)提到的直角三角形)。
矩形
設(shè)矩形R長(zhǎng)邊短邊各有m,n個(gè)格點(diǎ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)
直角三角形
易見兩條鄰邊和對(duì)角線組成的兩個(gè)直角三角形全等,且i,b相等。設(shè)其斜邊上有c個(gè)格點(diǎn)。
- 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
一般三角形
推廣
- 取格點(diǎn)的組成圖形的面積為一單位。在平行四邊形格點(diǎn),皮克定理依然成立。套用于任意三角形格點(diǎn),皮克定理則是A = 2i + b - 2。
- 對(duì)于非簡(jiǎn)單的多邊形P,皮克定理A = i + b/2 - χ(P),其中χ(P)表示P的歐拉特征數(shù)。
- 高維推廣:Ehrhart多項(xiàng)式;一維:植樹問題。
- 皮克定理和歐拉公式(V-E+F=2)等價(jià)。
定理提出者
Georg Alexander Pick,1859年生于維也納,1943年死于特萊西恩施塔特集中營(yíng)。
相關(guān)書籍
外部連結(jié)
en:Pick's theorem fr:Théorème de Pick it:Teorema di Pick pl:Wzór Picka ru:Теорема Пика
posted on 2009-10-06 17:59
wyiu 閱讀(145)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法