סכום מינוסקי

 

Minkowski Sum

הגדרה: Minkowski Sum עבור שני קבוצות S1,S2 במישור נתון ע"י שיוון הבא:

S1 Å S2 := { p+q: S1\'p, S2\'q}

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

וגם נגדיר: -S := { -p: S\'p }

משפט 1: בהינתן R – רובוט פוליגוני,

אז C-obstacle של P יהיה: PÅ(-R(0,0)).

הוכחה: צריך להוכיח ש-P נחתך עם R(x,y) אם"ם

P Å R(0,0)\'(x,y).וזה נובעת ישירות מהגדרת Minkowski Sum.

נתבונן במס\' תכונות של Minkowski Sum:

 

תכונה 1: בהינתן P ו R שני פוליגונים במישור, נקודה הקיצוניות של Minkowski Sum , P Å R בכיוון đ, יהיה סכום של קדקודים קיצונים בכיוון đ של P ו R.

הוכחה: נובע בקלות מהתכונות של כפל סקלרי של וקטורים.

משפט 2: בהינתן P ו R שני פוליגונים קמורים במישור בעלי n ו m קשתות בהתאם. אזי P Å R יהיה פוליגון קמור בעל m+n קשתות לכל היותר.וניתן לחישוב בזמן O(n+m).

הוכחה: קמורות של ש Minkowski Sumנובע ישירות מהגדרה, וכמות הקשתות נובע מכך שעבור קשת e של הסכום, הקשת זאת היא קיצונית בכיוון של הנורמל אליה, ולכן היא חייבת להיווצר ע"י לפחות נקודה קיצונית של P ו R באותו כיוון. יותר מזה לפחות קשת אחד מ P ו R חייבת להיות קיצונית באותו כיוון. ולכן לכול היותר ל Minkowski Sum יהיה m+n קשתות (במקרא ואין קווים מקבילים לP- ולR- אז זה יהיה בדיוק m+n).

 

בנוסף לכך הגבולות של שני Minkowski Sum  יכולים להיחתך בצורה מאוד מיוחדת, כדי לראות את זה נגדיר מוסג חדש.

הגדרה: pseudodiscs –זוג אובייקטים במישור O1 ו O2 נקראים pseudodiscs אם הם מקיימים תכונה הבא: קבוצות O1\O2 ו - O2\O1 הם רכיבים כשורים (ז"א מכל מקום ניתן להגיעה לכל מקום בקבוצה).

ואז קבוצת אובייקטים במישור נקראת קבוצת pseudodiscs אם כל זוג מקבוצה זאת הוא זוג של pseudodiscs.

 

תכונה 2: לכל זוג של pseudodiscs יש לכל היות 2 חיתוכים חוקיים על הגבול. התכונה זאת נובעת ישירות מהגדרה של pseudodiscs.

 

הגדרה: נגיד שפוליגון P1 יותר קיצוני מפוליגון  P2 בכיוון đ, אם נקודה קיצונית של  P1 בכיוון đ  נמצאת רחוק יותר  מנקודה קיצונית של P2 בכיוון đ.

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

 

תכונה 3: יהיה P1 ו P2 פוליגונים קמורים שלא נחתכים. ויהיה đ1 ו đ2 כיוונים בהם P1 קיצוני יותר מ - P2, אזי P1 קיצוני יותר    מ-P2 בכל הכיוונים מ- đ1 עד đ2 או קיצוני יותר בכל הכיוונים đ2 עד đ1.

 

 

ועכשיו אנו נוכיח ש- Minkowski Sumזהו pseudodiscs.

משפט 3: יהיה P1 ו P2 פוליגונים קמורים שלא נחתכים, ו R פוליגון קמור נוסף.אז P1 Å R ו P2 Å R הם pseudodiscs

הוכחה: נגדיר CP1 = R Å P1 ו-CP2 = R Å P2, ונוכיח ש CP2\ CP1רכיב קשיר יחיד. כיוון ש CP1ו CP2קמורים, אזי CP2\ CP1חייב להכיל על הגבול שלו נקודות מהקמור של CP2UCP1.

נניח בשלילה שיש יותר מרכיב קשירות אחד, זה אומר שיש שני כיוונים đ1 ו đ2, כך ש- CP1קיצוני יותר מ- CP2בשני הכיוונים האלו.מהתכונה 1 נובע שגם P1 קיצוני יותר מ-P2 בכיוונים אלו, ומתכונה 3 נובע

 ש-P1 קיצוני יותר מ-P2 בכל הכיוונים בין đ1 עד đ2, או בכל הכיוונים בין đ2 עד đ1.

 ואז שוב לפי תכונה 1 מקבלים שאותו דבר נכון לגבי  CP1ו- CP2בהתאם. וזה אומר שקבוצת הכיוונים בהם  CP1יותר קיצונית מ- CP2קשירה. וזה סתירה להנחה שיש יותר מרכיב קשירות אחד.

משפט 4: יהיה S אוסף של פסדודיסקים פוליגונים בעלי סה"כ n קשתות סה"כ, אז האיחוד שלהם בעל סיבוכיות O(n).

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

ישנם שני סוגי צמתים,

סוג א\': צמתים של איחוד שמקורם בצמתים מקוריים של פסדודיסקים.

סוג ב\': צמתים של איחוד שמקורם בחיתוך של פסדודיסקים.

ההתאמה של צמתים מסוג א\' פשוט לצמתים המקוריים של פסדודיסקים.

עבור צמתים מסוג ב\' נעשה התאמה באופן הבא:

יהיה v צומת הנוצר ע"י חיתוך של שני קשתות e1 ו e2 כאשר P1  \' e1 ו P2  \' e2, כאשר P1 ו P2 שייכים ל-S.(ראה ציור).

כיוון שקשת e1 נכנסת אל תוך פנים של P2 ישנם שני אפשרויות:

א.      e1 נגמר בתוך פנים של P2 ואז נטעים v לצומת הקצה של קשת e1 שנמצא בתוך P2.

ב.      אחרת e1 יוצאת מתוך P2, ואז נקודה שבא זה קורה זה נקודת חיתוך שניה בין P1 ל P2, ולכן לפי תכונות של פסדודיסקים e2 חייבת להיגמר בתוך פנים של P1. ולכן ל e2 חייב להיות צומת קצה בתוך פנים של P1 ולצומת הזה נוכל להטעים את צומת v.

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

ולכן קיבלנו שבאיחוד ישנם לכל היותר 2n צמתים. או במילים אחרות כמות הצמתים היא O(n).

 

ועכשיו אנו נביע אלגוריתם לחישוב Minkowski Sum.

משפט 5: יהי P וR  שני פוליגונים קמורים, בעלי n ו m צמתים בהתאם.

נוכל למצוא את P Å R בזמן O(n + m).

הוכחה: נביע אלגוריתם שמוצא את ה - P Å R.

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

האלגוריתם:

1.       נתחיל קדקודים בעלי קואורדינטת y הקטנה ביותר (ובעלי קואורדינטת x הקטנה ביותר במקרא ויש יותר מקודקוד אחד כזה) וזהו קדקודי ההתחלה וגם קדקודי סיום, ובנוסף הם גם יהיו קדקודים הנוכחים בצד ראשון. ונעשה טאטוא זוויתי על שני הפוליגונים במקביל, כאשר האירועים יהיו זוויות של קשתות של P ו-R כמו שהוגדר קודם.

2.       הוסף סכום של  קדקודים הנוכחים של R ושל P ל-Minkowski Sum.

3.       אם: זווית של P קטן מזווית של R, אז תתקדם לקודקוד הבא של P.

אחרת: אם: זווית של R קטן מזווית של P, אז תתקדם לקודקוד הבא של R.

אחרת: זווית של P שווה לזווית של R, אז תתקדם לקודקוד הבא של P וגם תתקדם לקודקוד הבא של R תחזור לצעד 2 כל עוד לא הגעתה בחזרה לקדקודי סיום של P וגם של R.

 

סיבוכיות: ברור שהאלגוריתם רץ בזמן O(n + m) כיוון שבכל צד של לולאה מתקדמים לפחות באחד הפוליגונים, וזה שהאלגוריתם מחשב את ה-Minkowski Sum נובע מתכונה 1, שרשומה מקודם. ומכך שאנו מוצאים את כל הזוגות של קדקודים קיצוניים בעזרת טאטוא על זוויות.

 

לאחר שמצאנו דרך למצוא Minkowski Sum לשני פוליגונים קמורים,

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

 

S1 Å (S2 U S3) = (S1 Å S2) (S1 Å S3)

 

בהתבסס על שיוון זה נוכל להוכיח משפט הבא:

משפט 6: יהי P וR  שני פוליגונים, בעלי n ו m צמתים בהתאם. סיבוכיות של מספר קשתות ב- P Å R יהיה:

א.      O (nm) במקרא ואחד הפוליגונים קמור והשני לא.

ב.      O (n²m²) במקרא ושני הפוליגונים לא קמורים.

הוכחה: נביע אלגוריתם שמוצא את ה - P Å R לשני המקרים

א.      כדי למצוא Minkowski Sum של פוליגון לא קמור P ופוליגון קמור R בעלי n ו m צמתים בהתאם, ואז נוכל לשלש את P ע"י n-2 משולשים t1,.., tn-2, ולפי שיוון הקודם לקבל

n

 P Å R = U (ti Å R)

I=1

ואז כיוון ש-  tiשמולשים ו R פוליגון קמור עם m צמתים אזי ti Å R היינו פוליגון קמור עם לכל היותר m+3 צמתים, וכיוון שמשולשים זרים בפנים שלהם אזי אוסף של  ti Å R היינו אוסף של  n-2 פסדודיסקים ולכן, כיוון  שהאיחוד שלהם ליניארי בסכום של הצמתים שלהם,

אזי הסיבוכיות של  P Å R תהיה O(nm) קשתות.

ולכן האלגוריתם כדי למצוא את Minkowski Sum במקרא כזה יהיה לשלש את P, לחשב את Minkowski Sum של כ"א מהמשולשים של שלוש ושל R ואז לאחד את כל ה- Minkowski Sumשקיבלנו.

 

ב.      כדי למצוא Minkowski Sum של שני פוליגונים לא קמורים P ו R בעלי n ו m צמתים בהתאם, ואזי נשלש את P ע"י n-2 משולשים t1, .., tn-2, ונשלש את R ע"י m-2 משולשים, u1, .., um-2.

ואז P Å R זהו איחוד של Minkowski Sum של הזוגות ti, uj. כ"א מ- ti Å uj בעל סיבוכיות קבוע (כי זהו Minkowski Sum של משולשים), ולכן P Å R זהו איחוד של (n-2)(m-2) פוליגונים בעלי סיבוכיות קבוע. ז"א יהיה O(nm) קשתות בכל הפוליגונים אלו. והסידור של כל הקשתות אלו יכול להיות לכל היותר O (n²m²) (לכל היותר כ"א נחתך עם כ"א).

 

וזהו החסם העליון של ה-Minkowski Sum, אבל האם זה באמת סיבוכיות במקרא הגרוע ביותר? התשובה היא כן, בתמונה רואים את הדוגמה לכך.

ולכן האלגוריתם  למציאת Minkowski Sum במקרא כזה יהיה לשלש את P ואת R, לחשב את Minkowski Sum של כ"א מהזוגות האפשריים של משולשים מהשלוש של P ושל R ואז לאחד את כל ה- Minkowski Sumשקיבלנו. כאשר אלגוריתם לאיחוד יהיה בהמשך.