Формула Пика для площади многоугольника на сетке

Введение

Формула площади сетчатого многоугольника. Теорема из комплексного анализа.

В геометрии теорема Пика предоставляет формулу для вычисления площади простого многоугольника с целочисленными координатами вершин, выраженную через количество целочисленных точек внутри него и на его границе. Результат был впервые описан Георгом Александром Пиком в 1899 году. Он стал широко известен на английском языке благодаря Хьюго Стейнхаусу в 1950 году в его книге «Математические зарисовки». Существует множество доказательств этой теоремы, и она может быть обобщена на формулы для определенных видов невыпуклых многоугольников.

Формула

Предположим, что многоугольник имеет целочисленные координаты для всех его вершин. Пусть *I* – количество целых точек внутри многоугольника, а *B* – количество целых точек на его границе (включая вершины и точки на сторонах). Тогда площадь *A* этого многоугольника равна:

На примере показано *I* внутренних точек и *B* граничных точек, поэтому его площадь равна квадратных единиц.

По формуле Эйлера

Одно из доказательств этой теоремы включает в себя разбиение многоугольника на треугольники с тремя целочисленными вершинами и без других целочисленных точек. Затем можно доказать, что каждый полученный треугольник имеет площадь ровно 1/2, поэтому площадь всего многоугольника равна половине числа треугольников в разбиении. Установив связь между площадью и количеством треугольников таким образом, доказательство завершается использованием полиэдрической формулы Эйлера для установления связи между количеством треугольников и количеством точек сетки в многоугольнике. Первая часть этого доказательства показывает, что треугольник с тремя целочисленными вершинами и без других целочисленных точек имеет площадь ровно 1/2, как утверждает формула Пика. В доказательстве используется тот факт, что любые треугольники могут покрыть плоскость, причем смежные треугольники повернуты на 180° друг относительно друга вокруг общего ребра. Для покрытий плоскости треугольниками с тремя целочисленными вершинами и без других целочисленных точек каждая точка целочисленной сетки является вершиной шести плиток. Поскольку число треугольников на точку сетки (шесть) вдвое больше, чем число точек сетки на треугольник (три), треугольники в два раза плотнее расположены на плоскости, чем точки сетки. Любая масштабированная область плоскости содержит в два раза больше треугольников (в пределе, когда масштабный фактор стремится к бесконечности), чем количество точек сетки, которые она содержит. Следовательно, каждый треугольник имеет площадь 1/2, что необходимо для доказательства. Другое доказательство того, что эти треугольники имеют площадь 1/2, основано на использовании теоремы Минковского о точках решетки в симметричных выпуклых множествах. Это уже доказывает формулу Пика для многоугольника, являющегося одним из этих специальных треугольников. Любой другой многоугольник можно разбить на специальные треугольники: добавляйте непересекающиеся отрезки внутри многоугольника между парами точек сетки, пока нельзя будет добавить больше отрезков. Единственные многоугольники, которые нельзя разбить таким образом, — это специальные треугольники, рассмотренные выше; следовательно, в полученном разбиении могут появляться только специальные треугольники. Поскольку каждый специальный треугольник имеет площадь 1/2, многоугольник площадью *A* будет разбит на *2A* специальных треугольников. Разбиение многоугольника на треугольники образует планарный граф, и формула Эйлера дает уравнение, применимое к числу вершин, ребер и граней любого планарного графа. Вершины — это просто точки сетки многоугольника, их *V*. Грани — это треугольники разбиения и единственная область плоскости за пределами многоугольника. Количество треугольников равно *T*, поэтому всего имеется *T+1* граней. Чтобы подсчитать ребра, заметим, что в разбиении имеется *3T* сторон треугольников. Каждое внутреннее ребро многоугольника является стороной двух треугольников. Однако имеется *B* ребер треугольников, лежащих вдоль границы многоугольника и являющихся частью только одного треугольника. Следовательно, число сторон треугольников удовлетворяет уравнению *3T = 2E + B*, из которого можно решить относительно числа ребер *E*. Подставив эти значения для *V*, *T* и *B* в формулу Эйлера *V - E + F = 1*, получим формулу Пика, полученную путем решения этого линейного уравнения относительно *A*. Альтернативный, но аналогичный расчет включает доказательство того, что число ребер того же разбиения равно *E*, что приводит к тому же результату. Также можно пойти в другом направлении, используя теорему Пика (доказанную другим способом) в качестве основы для доказательства формулы Эйлера.

One proof of this theorem involves subdividing the polygon into triangles with three integer vertices and no other integer points. One can then prove that each subdivided triangle has area exactly Therefore, the area of the whole polygon equals half the number of triangles in the subdivision. After relating area to the number of triangles in this way, the proof concludes by using Euler's polyhedral formula to relate the number of triangles to the number of grid points in the polygon. The first part of this proof shows that a triangle with three integer vertices and no other integer points has area exactly , as Pick's formula states. The proof uses the fact that all triangles tile the plane, with adjacent triangles rotated by 180° from each other around their shared edge. For tilings by a triangle with three integer vertices and no other integer points, each point of the integer grid is a vertex of six tiles. Because the number of triangles per grid point (six) is twice the number of grid points per triangle (three), the triangles are twice as dense in the plane as the grid points. Any scaled region of the plane contains twice as many triangles (in the limit as the scale factor goes to infinity) as the number of grid points it contains. Therefore, each triangle has area , as needed for the proof. A different proof that these triangles have area is based on the use of Minkowski's theorem on lattice points in symmetric convex sets. This already proves Pick's formula for a polygon that is one of these special triangles. Any other polygon can be subdivided into special triangles: add non crossing line segments within the polygon between pairs of grid points until no more line segments can be added. The only polygons that cannot be subdivided in this way are the special triangles considered above; therefore, only special triangles can appear in the resulting subdivision. Because each special triangle has area , a polygon of area will be subdivided into special triangles. The subdivision of the polygon into triangles forms a planar graph, and Euler's formula gives an equation that applies to the number of vertices, edges, and faces of any planar graph. The vertices are just the grid points of the polygon; there are of them. The faces are the triangles of the subdivision, and the single region of the plane outside of the polygon. The number of triangles is , so altogether there are faces. To count the edges, observe that there are sides of triangles in the subdivision. Each edge interior to the polygon is the side of two triangles. However, there are edges of triangles that lie along the polygon's boundary and form part of only one triangle. Therefore, the number of sides of triangles obeys the equation , from which one can solve for the number of edges, Plugging these values for , , and into Euler's formula gives

Pick's formula is obtained by solving this linear equation for An alternative but similar calculation involves proving that the number of edges of the same subdivision is , leading to the same result. It is also possible to go the other direction, using Pick's theorem (proved in a different way) as the basis for a proof of Euler's formula.

Другие доказательства

Альтернативные доказательства теоремы Пика, не использующие формулу Эйлера, включают следующее. Можно рекурсивно разложить данный многоугольник на треугольники, допуская, чтобы площадь некоторых треугольников в разбиении была больше 1/2. Как площадь, так и число точек, используемых в формуле Пика, складываются одинаковым образом, поэтому справедливость формулы Пика для общих многоугольников следует из её справедливости для треугольников. Любой треугольник разбивает свой ограничивающий прямоугольник на сам треугольник и дополнительные прямоугольные треугольники, а площади как ограничивающего прямоугольника, так и прямоугольных треугольников легко вычислить. Комбинируя эти вычисления площадей, получаем формулу Пика для треугольников, а комбинируя треугольники – формулу Пика для произвольных многоугольников. В качестве альтернативы, вместо использования квадратов сетки, центрированных на узлах сетки, можно использовать квадраты сетки, вершины которых находятся в узлах сетки. Эти квадраты сетки разрезают данный многоугольник на части, которые можно перестроить (путем сопоставления пар квадратов вдоль каждого ребра многоугольника) в полиомино с той же площадью. Теорему Пика также можно доказать, используя комплексное интегрирование двухпериодической функции, связанной с эллиптическими функциями Вейерштрасса. Применение формулы суммирования Пуассона к характеристической функции многоугольника приводит к другому доказательству. Теорема Пика была включена в веб-список "100 лучших математических теорем" в 1999 году, который позже Фрик Видейк использовал в качестве набора тестов для оценки мощности различных систем автоматического доказательства теорем. По состоянию на 2024 год теорема Пика была формализована и доказана только в одной из десяти систем автоматического доказательства теорем, зарегистрированных Видейком.

Обобщения

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

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

Связанные темы

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