Формула Пика
Рассмотрим невырожденный простой целочисленный многоугольник (т.е. он связный — любые две его точки могут быть соединены непрерывной кривой, целиком в нем содержащейся, и все его вершины имеют целые координаты, его граница — связная ломаная без самопересечений, и он имеет ненулевую площадь).
Для вычисления площади такого многоугольника можно воспользоваться следующей теоремой:
Теорема Пика. Пусть — число целочисленных точек внутри многоугольника,
— количество целочисленных точек на его границе,
— его площадь. Тогда справедлива формула Пика:
Пример. Для многоугольника на рисунке (желтые точки),
(синие точки, не забудьте о вершинах!), поэтому
квадратных единиц.
Вот здесь вы можете сами строить различные многоугольники, а площадь их будет вычислена по формуле Пика (многоугольники, присутствующие в этой статье, построены именно там).
Доказательство теоремы Пика. Сначала заметим, что формула Пика верна для единичного квадрата. Действительно, в этом случае мы имеем и
.
Рассмотрим прямоугольник со сторонами, лежащими на линиях решетки. Пусть длины его сторон равны и
. Имеем в этом случае
и, по формуле Пика,
Рассмотрим теперь прямоугольный треугольник с катетами, лежащими на осях координат. Такой треугольник получается из прямоугольника со сторонами и
, рассмотренного в предыдущем случае, разрезанием его по диагонали. Пусть на диагонали лежат
целочисленных точек. Тогда для этого случая
и получаем, что
Теперь рассмотрим произвольный треугольник. Его можно получить, отрезав от прямоугольника несколько прямоугольных треугольников и, возможно, прямоугольник (см. рисунки). Поскольку и для прямоугольника, и для прямоугольного треугольника формула Пика верна, мы получаем, что она будет справедлива и для произвольного треугольника.
Остается сделать последний шаг: перейти от треугольников к многоугольникам. Любой многоугольник можно разбить на треугольники (например, диагоналями). Поэтому нужно просто доказать, что при добавлении любого треугольника к произвольному многоугольнику формула Пика остается верной.
Пусть многоугольник и треугольник
имеют общую сторону. Предположим, что для
формула Пика справедлива, докажем, что она будет верна и для многоугольника, полученного из
добавлением
. Так как
и
имеют общую сторону, то все целочисленные точки, лежащие на этой стороне, кроме двух вершин, становятся внутренними точками нового многоугольника. Вершины же будут граничными точками. Обозначим число общих точек через
и получим
— число внутренних целочисленных точек нового многоугольника,
— число граничных точек нового многоугольника.
Из этих равенств получаем
Так как мы предположили, что теорема верна для и для
по отдельности, то
Тем самым, формула Пика доказана.
К сожалению, эта замечательная формула не обобщается на большие размерности, даже на трехмерный случай. Это показал Рив. Рассмотрим тетраэдр Рива, вершины которого имеют координаты
(Здесь — произвольное натуральное число.) При любом
внутри этого тетраэдра нет ни одной целочисленной точки, а на границе нет никаких целочисленных точек, кроме
и
. Таким образом, при различных объемах и площадях поверхностей данных тетраэдров число целочисленных точек, которые лежат внутри них и на их границах, остается неизменным, и обобщения формулы Пика получить не удается.
Однако некоторое обобщение получается с помощью полиномов Эрхарта.
Источники: http://en.wikipedia.org/wiki/Pick’s_theorem
http://e-maxx.ru/algo/pick_grid_theorem
1 Murad:
В мире существует только кубическая система координат, основание есть квадрат. Об этом в http://www.ferma.site40.net. То, что дана формула Пика ошибочно.
[Ответить]
14 Сентябрь 2011, 21:472 Георг Александр Пик (1859--1942) | Математика, которая мне нравится:
[...] Теорема Пика справедлива для многоугольников с вершинами в узлах целочисленной решетки. На плоскости образуется решетка двумя системами параллельных равноотстоящих прямых. [...]
30 Декабрь 2011, 0:07