משפט גרין דיסקרטי

מתוך ויקיפדיה, האנציקלופדיה החופשית

בחשבון אינפיניטסימלי, גרסאות דיסקרטיות של משפט גרין מתארות את הקשר בין אינטגרל כפול של פונקציה ב"תחום מלבני מוכלל" D (תחום שנוצר מאיחוד סופי של מלבנים במישור), וצירוף ליניארי של הפונקציה הקדומה של פונקציה נתונה, בפינות התחום. ערך זה מציג גרסה של משפט גרין הדיסקרטי [1] , המכלילה את אלגוריתם טבלת שטח מסוכם מתחום מלבני לאיחוד של כמה מלבנים.

המשפט נקרא על שם המתמטיקאי האנגלי ג'ורג' גרין, לאור הדמיון בינו לבין משפט גרין: שני המשפטים מתארים קשר בין אינטגרציה לאורך עקום, ואינטגרציה על תחום החסום על ידי העקום. משפט גרין הדיסקרטי מיושם בהקשרים של חישובי שטחים מהירים, החל מאפליקציות ממוחשבות כגון זיהוי אובייקטים בתמונה, וכלה בחישוב יעיל של הסתברויות.

המשפט[עריכת קוד מקור | עריכה]

הגדרת הפרמטר

תהי f פונקציה אינטגרבילית במישור, ותהי:

הפונקציה הקדומה שלה. יהי D תחום מלבני מוכלל במישור R2. אזי ניסוח המשפט הוא:

כאשר היא קבוצת הפינות של התחום הנתון D, ו - הוא פרמטר דיסקרטי עם ערכים אפשריים {0, ±1, ±2}, אשר נקבע על פי סוג הפינה, בהתאם לציור משמאל.

רעיון להוכחה[עריכת קוד מקור | עריכה]

כדי להוכיח את המשפט ניתן להפעיל את הנוסחא מהאלגוריתם טבלת שטח מסוכם על המרובעים שמרכיבים את התחום המלבני המקורי:

Proof discrete green.png

כפי שניתן לראות בתמונה לעיל, מקדמי הפונקציה הקדומה (+\-) מקזזים זה את לאורך המרובעים, מלבד פינות התחום המקורי.

דוגמה[עריכת קוד מקור | עריכה]

בהינתן פונקציה f שמוגדרת ב - R2, תהי F הפונקציה הקדומה שלה. יהי D התחום שצבוע בירוק בתמונה הבאה:

Discrete green illustration.png

אזי טענת המשפט לגבי התחום המלבני, היא:

הכללות[עריכת קוד מקור | עריכה]

פאם ושותפיו הציעו הכללה לתחומים פוליגוניאליים על ידי תכנון דינמי[2].

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ X. Wang, G. Doretto, T. Sebastian, J. Rittscher, and P. Tu. “Shape and appearance context modeling”. In Proc. IEEE Int. Conf. on Computer Vision (ICCV), pages 1–8, 2007. קישור למאמר
  2. ^ M. Pham, Y. Gao, V. D. Hoang, T. Cham. “Fast Polygonal Integration and Its Application in Extending Haar-like Features to Improve Object Detection”. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, CA, 2010. קישור למאמר