皮克定理

This post is written in Chinese. Please consider using Google Translate

皮克定理

给定顶点座标均是整点(或正方形格点)的简单多边形皮克定理说明了其面积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)等价

Related posts