Распечатать запись Распечатать запись

Формула Пика

Рассмотрим невырожденный простой целочисленный многоугольник (т.е. он связный — любые две его точки могут быть соединены непрерывной кривой, целиком в нем содержащейся, и все его вершины имеют целые координаты, его граница — связная ломаная без самопересечений, и он имеет ненулевую площадь).

Для вычисления площади такого многоугольника можно воспользоваться следующей теоремой:

Теорема Пика. Пусть L — число целочисленных точек внутри многоугольника, B — количество целочисленных точек на его границе, S — его площадь. Тогда справедлива формула Пика:

S=L+B/2-1 .

Пример. Для многоугольника на рисунке L=23 (желтые точки), B=7 (синие точки, не забудьте о вершинах!), поэтому S=23+7/2-1=25,5 квадратных единиц.

Вот здесь вы можете сами строить различные многоугольники, а площадь их будет вычислена по формуле Пика (многоугольники, присутствующие в этой статье, построены именно там).

Доказательство теоремы Пика. Сначала заметим, что формула Пика верна для единичного квадрата. Действительно, в этом случае мы имеем L=0,B=4 и S=0+4/2-1=1.

Рассмотрим прямоугольник со сторонами, лежащими на линиях решетки. Пусть длины его сторон равны a и b. Имеем в этом случае L=(a-1)(b-1), B=2a+2b и, по формуле Пика, S=(a-1)(b-1)+a+b-1=ab .

Рассмотрим теперь прямоугольный треугольник с катетами, лежащими на осях координат. Такой треугольник получается из прямоугольника со сторонами a и b, рассмотренного в предыдущем случае, разрезанием его по диагонали. Пусть на диагонали лежат c целочисленных точек. Тогда для этого случая \displaystyle L=\frac{(a-1)(b-1)-c+2}{2}, B=\frac{2a+2b}{2}+c-1 и получаем, что \displaystyle S=\frac{ab}{2} .

Теперь рассмотрим произвольный треугольник. Его можно получить, отрезав от прямоугольника несколько прямоугольных треугольников и, возможно, прямоугольник (см. рисунки). Поскольку и для прямоугольника, и для прямоугольного треугольника формула Пика верна, мы получаем, что она будет справедлива и для произвольного треугольника.



Остается сделать последний шаг: перейти от треугольников к многоугольникам. Любой многоугольник можно разбить на треугольники (например, диагоналями). Поэтому нужно просто доказать, что при добавлении любого треугольника к произвольному многоугольнику формула Пика остается верной.

Пусть многоугольник M и треугольник T имеют общую сторону. Предположим, что для M формула Пика справедлива, докажем, что она будет верна и для многоугольника, полученного из M добавлением T. Так как M и T имеют общую сторону, то все целочисленные точки, лежащие на этой стороне, кроме двух вершин, становятся внутренними точками нового многоугольника. Вершины же будут граничными точками. Обозначим число общих точек через c и получим

L_{MT}=L_M+L_T+(c-2) — число внутренних целочисленных точек нового многоугольника,

B_{MT}=B_M+B_T-2(c-2)-2 — число граничных точек нового многоугольника.

Из этих равенств получаем

L_M+L_P=L_{MT}-(c-2),B_M+B_P=B_{MT}+2(c-2)+2 .

Так как мы предположили, что теорема верна для M и для T по отдельности, то

S_{MT}=S_M+S_T=(L_M+B_M/2-1)+(L_T+B_T/2-1)=

=(L_M+L_T)+(B_M+B_T)/2-2=

= L_{MT}-(c-2)+(B_{MT}+2(c-2)+2)/2-2=

=L_{MT}+B_{MT}/2-1 .

Тем самым, формула Пика доказана.

К сожалению, эта замечательная формула не обобщается на большие размерности, даже на трехмерный случай. Это показал Рив. Рассмотрим тетраэдр Рива, вершины которого имеют координаты

A(0,0,0),B(1,0,0),C(0,1,0),D(1,1,k) .

(Здесь k — произвольное натуральное число.) При любом k внутри этого тетраэдра нет ни одной целочисленной точки, а на границе нет никаких целочисленных точек, кроме A,B,C и D. Таким образом, при различных объемах и площадях поверхностей данных тетраэдров число целочисленных точек, которые лежат внутри них и на их границах, остается неизменным, и обобщения формулы Пика получить не удается.

Однако некоторое обобщение получается с помощью полиномов Эрхарта.

Источники: http://en.wikipedia.org/wiki/Pick’s_theorem
http://e-maxx.ru/algo/pick_grid_theorem

Комментариев: 2

  1. 1 Murad:

    В мире существует только кубическая система координат, основание есть квадрат. Об этом в http://www.ferma.site40.net. То, что дана формула Пика ошибочно.

    [Ответить]

  2. 2 Георг Александр Пик (1859--1942) | Математика, которая мне нравится:

    [...] Теорема Пика справедлива для многоугольников с вершинами в узлах целочисленной решетки. На плоскости образуется решетка двумя системами параллельных равноотстоящих прямых. [...]

Оставьте свой отзыв

Добавить изображение