Теорема Піка

Многокутник без самоперетинів називають ґратковим, якщо всі його вершини мають цілочислові координати в деякій 2D-ґратці. Теорема Піка дає спосіб обчислити площу такого многокутника через кількість вершин, що лежать на межі, та кількість вершин, що лежать строго всередині многокутника.

Формула

Нехай задано деякий ґратковий многокутник із ненульовою площею.

Позначимо його площу через $S$, кількість точок із цілочисловими координатами, що лежать строго всередині многокутника, через $I$, а кількість точок, що лежать на сторонах многокутника, через $B$.

Тоді формула Піка стверджує:

$$S=I+\frac{B}{2}-1$$

Зокрема, якщо для многокутника задано значення $I$ та $B$, площу можна обчислити за $O(1)$, навіть не знаючи самих вершин.

Цю формулу відкрив і довів австрійський математик Георг Александер Пік у 1899 році.

Доведення

Доведення проводиться в багато етапів: від простих многокутників до довільних:

• Один квадрат: $S=1, I=0, B=4$, що задовольняє формулу.

• Довільний невироджений прямокутник зі сторонами, паралельними осям координат: нехай $a$ і $b$ — довжини сторін прямокутника. Тоді $S=ab, I=(a-1)(b-1), B=2(a+b)$. Підставивши, ми бачимо, що формула правдива.

• Прямий кут із катетами, паралельними осям: щоб це довести, зауважимо, що будь-який такий трикутник можна отримати, відрізавши прямокутник по діагоналі. Позначивши кількість цілочислових точок, що лежать на діагоналі, через $c$, можна показати, що формула Піка виконується для цього трикутника незалежно від $c$.

• Довільний трикутник: зауважимо, що будь-який такий трикутник можна перетворити на прямокутник, приєднавши до його сторін прямокутні трикутники з катетами, паралельними осям (вам знадобиться не більш ніж 3 такі трикутники). Звідси ми можемо отримати правильну формулу для будь-якого трикутника.

• Довільний многокутник: щоб це довести, тріангулюємо його, тобто розіб'ємо на трикутники з цілочисловими координатами. Далі можна довести, що теорема Піка зберігає свою справедливість, коли до трикутника додають многокутник. Отже, ми довели формулу Піка для довільного многокутника.

Узагальнення на вищі розмірності

На жаль, цю просту й красиву формулу не можна узагальнити на вищі розмірності.

Джон Рів продемонстрував це, запропонувавши 1957 року тетраедр (тетраедр Ріва) з такими вершинами:

$$A=(0,0,0), B=(1,0,0), C=(0,1,0), D=(1,1,k),$$

де $k$ може бути будь-яким натуральним числом. Тоді для будь-якого $k$ тетраедр $ABCD$ не містить жодної цілочислової точки всередині себе і має лише $4$ точки на своїх межах: $A, B, C, D$. Отже, об'єм і площа поверхні можуть змінюватися, попри незмінну кількість точок усередині та на межі. Тому теорема Піка не допускає узагальнень.

Проте у вищих розмірностях усе ж є узагальнення за допомогою многочленів Ергарта, але вони доволі складні й залежать не лише від точок усередині, а й від межі політопа.

Додаткові ресурси

Кілька простих прикладів і просте доведення теореми Піка можна знайти тут.