Теорема Піка

Щодо відповідної теореми в комплексномі аналізі див. Теорема Піка (комплексний аналіз).

i = 7, b = 8, S = i + b/2 − 1 = 10

Трикутник з вершинами в нижній лівій, нижній правій, та верхній правій точках i = 12 та b = 14, відповідно до теореми Піка S = i + b/2 − 1 = 18; це підтверджує формулі площі для трикутника 1/2 × основа × висота = 1/2 × 9 × 4 = 18.

Якщо розглянути простий многокутник, побудований на сітці рівновіддалених точок (тобто точок з цілими координатами), так, що всі вершини многокутника є точками сітки, теорема Піка дає просту формулу для обчислення площі ${\displaystyle S}$ цього многокутника, за кількістю ${\displaystyle i}$ (точок решітки усередині фігури) і кількістю ${\displaystyle b}$ (точок решітки), розміщених по периметру многокутника:

${\displaystyle S=i+{\frac {b}{2}}-1.}$

У наведеному прикладі маємо i = 7 (внутрішніх точок) і b = 8 (граничних точок), так що площа ${\displaystyle A}$ = 7 + 8/2 − 1 = 7 + 4 − 1 = 10 квадратних одиниць.

Вищенаведена теорема справедлива лише для простих многокутників, тобто для тих, які складаються з єдиної межі, без перетинів і дірок. Для загального многокутника формула Піка має такий вигляд:

${\displaystyle S=v-{\frac {1}{2}}e_{b}+h-1}$,

де ${\displaystyle v}$ — кількість вершин всередині і на межі многокутника, ${\displaystyle e_{b}}$ — кількість точок решітки на межі многокутника, і ${\displaystyle h}$ — кількість дірок у многокутнику.

Як приклад розглянемо многокутник, побудований за допомогою точок ${\displaystyle (0,0),(2,0)}$. Він має 3 вершини, 0 отворів і 0 область. Щоб формула працювала, повинно бути 4 ребра. Таким чином, треба просто порахувати кожен край двічі, один раз на кожній стороні.^[]

Результат вперше описав Георг Александр Пік в 1899. Тетраедр Ріва демонструє, що немає аналогу теореми Піка в розмірності три, яка виражає об'єм многогранника через кількість внутрішніх і граничних точок. Однак є узагальнення для вищих розмірностей через многочлени Ергарта.

Доведення

Розглянемо многокутник ${\displaystyle P}$ і трикутник ${\displaystyle T}$, що має з ${\displaystyle P}$ одне спільне ребро. Припустимо, що теорема Піка справедлива як для ${\displaystyle P}$, так і для ${\displaystyle T}$ незалежно один від одного; ми хочемо показати, що це також справедливо для многокутника ${\displaystyle PT}$, отриманого шляхом додавання ${\displaystyle T}$ до ${\displaystyle P}$. Оскільки ${\displaystyle P}$ і ${\displaystyle T}$ маю одне спільне ребро, всі граничні точки уздовж цього ребра стають внутрішніми точками, за винятком двох кінцевих точок, які об'єднуються з граничними точками. Отже, якщо ${\displaystyle C}$ кількість спільних граничних точок, то маємо:

${\displaystyle i_{PT}=i_{P}+i_{T}+(c-2)}$

і

${\displaystyle b_{PT}=b_{P}+b_{T}-2(c-2)-2.}$

З вищезазначеного випливає:

${\displaystyle i_{P}+i_{T}=i_{PT}-(c-2)}$

і

${\displaystyle b_{P}+b_{T}=b_{PT}+2(c-2)+2.}$

Оскільки ми припускаємо виконання теореми і для ${\displaystyle P}$ і для ${\displaystyle T}$, то:

${\displaystyle {\begin{aligned}S_{PT}&=S_{P}+S_{T}\\&=\left(i_{P}+{\frac {b_{P}}{2}}-1\right)+\left(i_{T}+{\frac {b_{T}}{2}}-1\right)\\&=i_{P}+i_{T}+{\frac {b_{P}+b_{T}}{2}}-2\\&=i_{PT}-(c-2)+{\frac {b_{PT}+2(c-2)+2}{2}}-2\\&=i_{PT}+{\frac {b_{PT}}{2}}-1.\end{aligned}}}$

Тому, якщо теорема справедлива для многокутників побудованих з ${\displaystyle n}$ трикутників, вона справедлива і для многокутників, що побудовані з n + 1трикутника. Добре відомо, що довільний многокутник можна розбити на симплекси тріангуляція. Це тривіальний факт у випадку площини. Для завершення доведення методом математичної індукції достатньо довести її у випадку трикутників. Перевірку цього випадку здійснюється за допомогою наступних коротких кроків:

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

На останньому кроці застосовується той факт, що якщо теорема справедлива для многокутника ${\displaystyle PT}$ і для трикутника ${\displaystyle T}$, то це також має місце для многокутника ${\displaystyle P}$; це можна побачити на основі обчислень, які подібні до наведених вище.

Нерівність для опуклих множин

Нехай ${\displaystyle C}$ — обмежена, опукла область в ${\displaystyle \mathbb {R} ^{2}}$, не обов'язково замкнена. Тоді:

${\displaystyle |L(C)|\leq {\text{площа}}(C)+{\frac {1}{2}}{\text{периметр}}(C)+1}$,

де ${\displaystyle L(C)}$ — це набір точок решітки в ${\displaystyle C}$, і ${\displaystyle |L(C)|}$ — їх кількість. Рівність має місце тоді і лише тоді, коли ${\displaystyle C}$ — замкнений многокутник решітки. Для доведення розглянемо опуклий оболонку ${\displaystyle {\bar {C}}}$ для ${\displaystyle L(C)}$, яку слід розуміти як наближення решітки для області ${\displaystyle C}$, а потім застосуємо до неї теорему Піка:

${\displaystyle {\begin{aligned}|L(C)|=|L({\bar {C}})|&={\text{площа}}({\bar {C}})+{\frac {1}{2}}B({\bar {C}})+1\\&\leq {\text{площа}}({\bar {C}})+{\frac {1}{2}}{\text{периметр}}({\bar {C}})+1\\&\leq {\text{площа}}(C)+{\frac {1}{2}}{\text{периметр}}(C)+1,\end{aligned}}}$

де ${\displaystyle B({\bar {C}})}$ — кількість граничних точок ${\displaystyle {\bar {C}}}$, що дорівнює кількості його ребер, і оскільки кожне ребро має мінімальну довжину 1, то:

${\displaystyle B({\bar {C}})\leq {\text{периметр}}({\bar {C}})}$.

Перехід ${\displaystyle {\text{периметр}}({\bar {C}})\leq {\text{периметр}}(C)}$ використовує властивість, що між двома вкладеними, опуклими, замкнутими кривими, внутрішня крива буде коротшою на основі прямого застосування формули Крофтона.

Формула залишається справедливою і у виродженому випадку, коли ${\displaystyle L(C)}$ знаходиться на одній лінії. Потрібно просто порахувати кожен ребро двічі (по одному разу з кожної сторони).

Див. також

• ^[en]
• ^[en]
• Послідовність Фарі
• Многочлен Ергарта

Література

1. Trainin, J. (November 2007). An elementary proof of Pick's theorem. 91 (522): 536—540. doi:10.1017/S0025557200182270.
2. Garbett, Jennifer (18 листопада 2010). (PDF). Архів оригіналу (PDF) за 29 серпня 2017.
3. Belyaev, Alexander; Fayolle, Pierre-Alain (8 серпня 2019). Counting Parallel Segments: New Variants of Pick's Area Theorem (англ.). 41 (4): 1—7. doi:10.1007/s00283-019-09921-8. ISSN 0343-6993.
4. Pick, Georg (1899). . Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen "Lotos" in Prag. (Neue Folge). 19: 311—319. Архів оригіналу за 1 березня 2017. Процитовано 26 травня 2020. CiteBank:47270 [ 6 жовтня 2014 у Wayback Machine.]
5. Beck, Matthias; Robins, Sinai (2007). Computing the Continuous Discretely: Integer-point enumeration in polyhedra. New York: Springer-Verlag. ISBN .