הסריקה של גראהם

הסריקה של גראהם, על שם המתמטיקאי רונלד גראהם, הוא אלגוריתם למציאת הקמור של קבוצת נקודות במישור, בסיבוכיות של $\ \Theta (n\log n)$ , כאשר $\ n$ הוא מספר הנקודות.

תיאור האלגוריתם

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

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

אם מיון הנקודות נעשה על בסיס קוארדינטת $\ x$ שלהן, יהיה צורך בשתי סריקות כדי לבנות את הקמור - אחת בשביל הנקודות שנמצאות מעל לשתי הנקודות בעלות קואורדינטות ה- $\ x$ הקיצוניות, ואחת בשביל הנקודות שמתחתן. אם ממיינים את הנקודות על בסיס הזווית שהן יוצרות עם ציר $\ x$ המועבר דרך אחת מהנקודות הקיצוניות, די בסריקה אחת.

סיבוכיות האלגוריתם

ראשית, מיון הנקודות שנעשה לפני תחילת הסריקה יכול להתבצע בסיבוכיות $\ O(n\log n)$ (אך לא טוב יותר, שכן זהו גם חסם תחתון על מיון כללי). הסריקה עצמה, בניתוח הגס ביותר, היא בסיבוכיות $\ O(n^{2})$ , שכן מכניסים $\ n$ איברים למחסנית (כל נקודה נכנסת למחסנית בשלב כלשהו) ועבור כל הכנסה של איבר למחסנית, ייתכן שיוצאו ממנה כל האיברים פרט לשניים. מכיוון שהמחסנית יכולה להכיל עד $\ n$ איברים, מתקבלת הסיבוכיות $\ O(n^{2})$ .

אולם, ניתוח עדין מעט יותר מראה כי הסיבוכיות היא למעשה $\ O(n)$ . זאת מכיוון שכל איבר יכול להיות מוצא מהמחסנית פעם אחת בדיוק (שכן מרגע שאיבר הוצא מהמחסנית הוא אינו מוחזר יותר). על כן, מתבצעות על המחסנית לכל היותר $\ 2\cdot n$ פעולות: הכנסה ו(אולי) הוצאה של כל אחד מ- $\ n$ הנקודות.

ניתן להראות כי אלגוריתם כלשהו למציאת קמור יכול לשמש גם למיון, ומכיוון שקיים למיון כללי חסם תחתון $\ \Omega (n\log n)$ נובע מכך שגם סיבוכיות הסריקה של גראהם היא $\ \Omega (n\log n)$ . לכן בסך הכל, הסיבוכיות של הסריקה היא בדיוק $\ \Theta (n\log n)$ .