пятница, 25 октября 2013 г.

Формула Пика

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


Теорема Пика. Пусть 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. Таким образом, при различных объемах и площадях поверхностей данных тетраэдров число целочисленных точек, которые лежат внутри них и на их границах, остается неизменным, и обобщения формулы Пика получить не удается.
Однако некоторое обобщение получается с помощью полиномов Эрхарта.

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

Отправить комментарий