Формула Пика

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

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

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

Пример. Для многоугольника на рисунке  (желтые точки),  (синие точки, не забудьте о вершинах!), поэтому  квадратных единиц.

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

Доказательство теоремы Пика. Сначала заметим, что формула Пика верна для единичного квадрата. Действительно, в этом случае мы имеем  и .

Рассмотрим прямоугольник со сторонами, лежащими на линиях решетки. Пусть длины его сторон равны  и . Имеем в этом случае  и, по формуле Пика, 

Рассмотрим теперь прямоугольный треугольник с катетами, лежащими на осях координат. Такой треугольник получается из прямоугольника со сторонами  и , рассмотренного в предыдущем случае, разрезанием его по диагонали. Пусть на диагонали лежат  целочисленных точек. Тогда для этого случая  и получаем, что 

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

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

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

 — число внутренних целочисленных точек нового многоугольника,

 — число граничных точек нового многоугольника.

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

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

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

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

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

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

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