Теорема Піка

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

i = 7

,

b = 8

,

S = i + b 2 - 1 = 10

Трикутник з вершинами в нижній лівій, нижній правій, та верхній правій точках

i = 12

та

b = 14

, відповідно до теореми Піка

S = i + b 2 - 1 = 18

; це підтверджує формулі площі для трикутника 12 × основа × висота = 12 × 9 × 4 = 18.

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

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

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

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

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

,

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

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

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

Доведення

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

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

і

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

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

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

і

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

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

{\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}}

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

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

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

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

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

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

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

{\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}}

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

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

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

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

Див. також

Цілі точки в опуклих багатогранниках
Довгомір Штайнгауза
Послідовність Фарі
Многочлен Ергарта

Література

Trainin, J. (November 2007). An elementary proof of Pick's theorem 91 (522). с. 536–540. doi:10.1017/S0025557200182270.
Garbett, Jennifer (18 листопада 2010). Lattice Point Geometry: Pick's Theorem and Minkowski's Theorem, Senior Exercise in Mathematics. Архів оригіналу за 29 серпня 2017.
Belyaev, Alexander; Fayolle, Pierre-Alain (8 серпня 2019). Counting Parallel Segments: New Variants of Pick's Area Theorem (англ.) 41 (4). с. 1–7. ISSN 0343-6993. doi:10.1007/s00283-019-09921-8.
Pick, Georg (1899). Geometrisches zur Zahlenlehre. Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen "Lotos" in Prag. (Neue Folge) 19: 311–319. CiteBank:47270
Beck, Matthias; Robins, Sinai (2007). Computing the Continuous Discretely: Integer-point enumeration in polyhedra. New York: Springer-Verlag. ISBN 978-0-387-29139-0.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Trainin, J. (November 2007). An elementary proof of Pick's theorem 91 (522). с. 536–540. doi:10.1017/S0025557200182270.

[:0-2] Garbett, Jennifer (18 листопада 2010). Lattice Point Geometry: Pick's Theorem and Minkowski's Theorem, Senior Exercise in Mathematics. Архів оригіналу за 29 серпня 2017.

[3] Belyaev, Alexander; Fayolle, Pierre-Alain (8 серпня 2019). Counting Parallel Segments: New Variants of Pick's Area Theorem (англ.) 41 (4). с. 1–7. ISSN 0343-6993. doi:10.1007/s00283-019-09921-8.

[4] Pick, Georg (1899). Geometrisches zur Zahlenlehre. Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen "Lotos" in Prag. (Neue Folge) 19: 311–319. CiteBank:47270

[5] Beck, Matthias; Robins, Sinai (2007). Computing the Continuous Discretely: Integer-point enumeration in polyhedra. New York: Springer-Verlag. ISBN 978-0-387-29139-0.