יחידה 2: מעטפות קמורות

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

הגדרת המעטפת הקמורה וחשיבותה

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

חשיבות המעטפת הקמורה:

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

אלגוריתמים למציאת מעטפת קמורה

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

סריקת גרהם (Graham Scan)

אלגוריתם יעיל למציאת מעטפת קמורה, המתבסס על מיון ושימוש במחסנית.

שלבי האלגוריתם:

1. מציאת נקודת עוגן: מוצאים את הנקודה בעלת קואורדינטת ה-Y המינימלית (ובמקרה של שוויון, את זו בעלת קואורדינטת ה-X המינימלית). נקודה זו בוודאות שייכת למעטפת הקמורה. נסמנה P0.
2. מיון: ממיינים את שאר הנקודות (P1, ..., Pn-1) לפי הזווית שהן יוצרות עם P0 והציר החיובי של X. במקרה של שוויון זוויות, הנקודה הקרובה יותר ל-P0 תבוא קודם.
3. בניית המעטפת באמצעות מחסנית:
   • מכניסים למחסנית את P0, P1, P2.
   • עוברים על שאר הנקודות הממוינות (החל מ-P3). עבור כל נקודה Pi:
     • כל עוד יש לפחות שתי נקודות במחסנית, והפנייה מפסגת המחסנית השנייה, דרך פסגת המחסנית, אל Pi היא פנייה ימינה (או קו ישר, במקרה של נקודות קולינאריות שאינן קצה), מוציאים את פסגת המחסנית.
     • מכניסים את Pi למחסנית.

סיבוכיות: O(N log N) בעיקר בגלל שלב המיון. שלב בניית המעטפת לוקח O(N).

צעד ג'רוויס (Jarvis March / Gift Wrapping)

אלגוריתם אינטואיטיבי המדמה "עטיפת מתנה" סביב הנקודות.

שלבי האלגוריתם:

1. מציאת נקודת התחלה: מוצאים את הנקודה הקיצונית ביותר (לרוב, הנקודה בעלת קואורדינטת ה-Y המינימלית, ובמקרה של שוויון, ה-X המינימלית). נקודה זו היא Pstart.
2. בניית המעטפת:
   • הנקודה הנוכחית (current_point) היא Pstart.
   • חוזרים על הפעולות הבאות עד שחוזרים ל-Pstart:
     • מוצאים את הנקודה הבאה (next_point) במעטפת. זוהי הנקודה מבין כל שאר הנקודות שיוצרת את הזווית הקטנה ביותר (נגד כיוון השעון) עם current_point ווקטור הייחוס (לרוב, ציר ה-X השלילי או הווקטור מ-current_point לנקודה הקודמת במעטפת).
     • מוסיפים את next_point למעטפת.
     • current_point הופכת ל-next_point.

סיבוכיות: O(N * h), כאשר N הוא מספר הנקודות הכולל ו-h הוא מספר הנקודות על המעטפת הקמורה. במקרה הגרוע ביותר (כשכל הנקודות על המעטפת), הסיבוכיות היא O(N^2).

אלגוריתם חלוק והפרד (Divide and Conquer)

גישה רקורסיבית המבוססת על פירוק הבעיה לבעיות קטנות יותר.

שלבי האלגוריתם:

1. מיון: ממיינים את כל הנקודות לפי קואורדינטת ה-X.
2. חלוקה: מחלקים את קבוצת הנקודות לשתי תת-קבוצות בגודל שווה (שמאל וימין).
3. הפרד: מוצאים את המעטפת הקמורה לכל תת-קבוצה באופן רקורסיבי.
4. מזג: ממזגים את שתי המעטפות הקמורות (השמאלית והימנית) למעטפת קמורה אחת. שלב המיזוג הוא המורכב ביותר וכולל מציאת שני משיקים משותפים (עליון ותחתון) בין שתי המעטפות.

סיבוכיות: O(N log N). שלב המיזוג לוקח O(N).

שאלות לדיון

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

נקודות לתשובת מודל

• הבדל מהותי: גרהם ממיין את כל הנקודות מראש ובונה את המעטפת במעבר אחד באמצעות מחסנית. ג'רוויס בונה את המעטפת נקודה אחר נקודה, כאשר בכל שלב הוא מחפש את הנקודה הבאה מכלל הנקודות הנותרות.
• חשיבות המיון בגרהם: המיון לפי זווית מבטיח שהנקודות נבדקות בסדר מעגלי סביב נקודת העוגן. זה מאפשר את השימוש במחסנית ובבדיקת הפניות לשמירה על קמירות. סיבוכיות המיון (O(N log N)) היא הגורם הדומיננטי בסיבוכיות הכוללת של האלגוריתם.
• יעילות ג'רוויס: ג'רוויס יעיל יותר כאשר מספר הנקודות על המעטפת (h) קטן מאוד (למשל, h קבוע), מכיוון שסיבוכיותו היא O(N*h). לעומת זאת, כאשר h קרוב ל-N, סיבוכיותו מתדרדרת ל-O(N^2), וגרהם (O(N log N)) עדיף.
• אתגר המיזוג בחלוק והפרד: האתגר הוא למצוא את שני המשיקים המשותפים (עליון ותחתון) בין שתי המעטפות הקמורות (שכבר נמצאו). זה נעשה בדרך כלל על ידי אלגוריתם איטרטיבי המחפש את הנקודות המתאימות בשתי המעטפות, תוך שימוש בבדיקות פנייה.
• טיפול בנקודות קולינאריות:
  • גרהם: בשלב המיון, אם מספר נקודות קולינאריות עם P0, יש למיין אותן לפי מרחק מ-P0 (הקרובה קודם). בשלב המחסנית, פנייה "ישרה" (תוצאת מכפלה וקטורית אפס) יכולה להיחשב כ"ימינה" כדי להסיר נקודות פנימיות.
  • ג'רוויס: בעת מציאת הנקודה הבאה, אם מספר נקודות יוצרות את אותה זווית מינימלית, יש לבחור את הנקודה הרחוקה ביותר מהנקודה הנוכחית כדי להבטיח שהנקודות הפנימיות לא ייכללו.