پرش به محتویات

قضیه پیک

یک چندضلعی ساده (بدون خود-برخورد) را شبکه‌ای می‌نامیم اگر تمام رئوس آن در یک شبکه دو بعدی دارای مختصات صحیح باشند. قضیه پیک راهی برای محاسبه مساحت این چندضلعی با استفاده از تعداد نقاطی که روی مرز آن قرار دارند و تعداد نقاطی که کاملاً درون آن قرار دارند، ارائه می‌دهد.

فرمول

یک چندضلعی شبکه‌ای با مساحت غیر صفر را در نظر بگیرید.

مساحت آن را با $S$، تعداد نقاط با مختصات صحیح که کاملاً درون چندضلعی قرار دارند را با $I$ و تعداد نقاطی که روی اضلاع چندضلعی قرار دارند را با $B$ نمایش می‌دهیم.

در این صورت، فرمول پیک بیان می‌کند:

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

به طور خاص، اگر مقادیر $I$ و $B$ برای یک چندضلعی داده شده باشند، مساحت آن را می‌توان در زمان $O(1)$ و حتی بدون دانستن رئوس آن محاسبه کرد.

این فرمول در سال ۱۸۹۹ توسط ریاضیدان اتریشی، گئورگ الکساندر پیک، کشف و اثبات شد.

اثبات

اثبات در چند مرحله انجام می‌شود: از چندضلعی‌های ساده شروع کرده و به چندضلعی‌های دلخواه می‌رسیم:

  • یک مربع واحد: $S=1, I=0, B=4$ که در فرمول صدق می‌کند.

  • یک مستطیل دلخواه غیرتبهگن با اضلاع موازی با محورهای مختصات: فرض کنید طول اضلاع مستطیل $a$ و $b$ باشند. در این صورت داریم $S=ab, I=(a-1)(b-1), B=2(a+b)$. با جایگذاری این مقادیر، می‌بینیم که فرمول درست است.

  • یک مثلث قائم‌الزاویه با ساق‌های موازی با محورها: برای اثبات این مورد، توجه کنید که هر مثلث این‌چنینی را می‌توان با بریدن یک مستطیل توسط قطر آن به دست آورد. با فرض اینکه $c$ تعداد نقاط صحیح روی قطر باشد، می‌توان نشان داد که فرمول پیک برای این مثلث، صرف‌نظر از مقدار $c$، برقرار است.

  • یک مثلث دلخواه: توجه کنید که هر مثلثی را می‌توان با الحاق مثلث‌های قائم‌الزاویه‌ای با ساق‌های موازی با محورها به آن، به یک مستطیل تبدیل کرد (به بیش از ۳ مثلث از این نوع نیاز نخواهید داشت). از اینجا می‌توان فرمول صحیح را برای هر مثلثی استخراج کرد.

  • یک چندضلعی دلخواه: برای اثبات، آن را مثلث‌بندی می‌کنیم، یعنی آن را به مثلث‌هایی با رئوس دارای مختصات صحیح تقسیم می‌کنیم. علاوه بر این، می‌توان اثبات کرد که وقتی یک مثلث به یک چندضلعی (که در قضیه صدق می‌کند) اضافه شود، قضیه پیک برای چندضلعی جدید نیز معتبر باقی می‌ماند. به این ترتیب، فرمول پیک را برای هر چندضلعی دلخواهی اثبات کرده‌ایم.

تعمیم به ابعاد بالاتر

متأسفانه، این فرمول ساده و زیبا را نمی‌توان به ابعاد بالاتر تعمیم داد.

جان ریو (John Reeve) در سال ۱۹۵۷ با معرفی یک چهاروجهی (چهاروجهی Reeve) با رئوس زیر این موضوع را نشان داد:

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

که در آن $k$ می‌تواند هر عدد طبیعی باشد. در این صورت برای هر مقدار $k$، چهاروجهی $ABCD$ هیچ نقطه صحیحی در داخل خود ندارد و فقط ۴ نقطه روی مرزهایش دارد که همان رئوس $A, B, C, D$ هستند. بنابراین، حجم و مساحت سطح می‌توانند با وجود ثابت ماندن تعداد نقاط داخلی و مرزی، متغیر باشند. در نتیجه، قضیه پیک تعمیم‌پذیر نیست.

با این حال، برای ابعاد بالاتر تعمیمی با استفاده از چندجمله‌ای‌های Ehrhart وجود دارد، اما این چندجمله‌ای‌ها بسیار پیچیده هستند و نه تنها به نقاط داخلی، بلکه به مرز چندوجهی (polytope) نیز بستگی دارند.

منابع بیشتر

چند مثال ساده و یک اثبات ساده برای قضیه پیک را می‌توانید اینجا پیدا کنید.