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

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

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

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

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

''הסריקה של גראהם'' הוא אלגוריתם למציאת הקמור של קבוצת נקודות. הקמור הוא הקו החיצוני שמקיף את כל הנקודות.

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

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

אם מסדרים לפי ה-x עושים שתי מסירות, עליונה ותחתונה. אם מסדרים לפי זווית יחסית לנקודה קיצונית, מספיק לעבור פעם אחת.

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