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

בגאומטריה חישובית, אלגוריתם טאטוא (בתרגום חופשי אלגוריתם קו-סורק) (sweep line algorithm) או אלגוריתם טאטוא מישור (או סחיפה) (plane sweep algorithm) הוא פרדיגמה אלגוריתמית המשתמשת בקו סורק רעיוני או במשטח סורק כדי לפתור בעיות שונות במרחב האוקלידי. זהו אחד הכלים המרכזיים בתחום הגאומטריה החישובית.^[1]

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

יישומים

יישום של גישה זו הביא לפריצת דרך במורכבות החישובית של אלגוריתמים גאומטריים, כאשר בשנת 1976 הציגו שאמוס (Shamos) והוי (Hoey) אלגוריתמים למציאת חיתוכים של מקטעים במישור.^[2] בפרט, הם הראו כי שילוב של שיטת קו הסריקה עם מבני נתונים יעילים (כגון עצי חיפוש מאוזנים) מאפשר לזהות האם קיימים חיתוכים בין $N$ מקטעים במישור בזמן חישוב של $O (N l o g (N))$ .

אלגוריתם קשור, אלגוריתם בנטלי–אוטמן(אנ') (Bentley–Ottmann), עושה שימוש בטכניקת קו סורק כדי לדווח על כל $K$ החיתוכים בין $N$ מקטעים במישור בזמן חישוב של $O ((N + K) l o g N)$ ובמורכבות זיכרון של $O (N)$ .^[3] מאז, גישה זו שימשה לעיצוב אלגוריתמים יעילים לבעיות רבות בגאומטריה חישובית, כגון בניית דיאגרמת וורונוי (באמצעות אלגוריתם פורצ'ן), טריאנגולציית דלוני, וכן ביצוע פעולות בוליאניות על פוליגונים.

הכללות והרחבות

סחיפה טופולוגית (topological sweeping) היא גרסה של קו סורק שבה סדר העיבוד של הנקודות פשוט יותר, ואינה דורשת מיון מלא של כל הנקודות; הדבר מאפשר ביצוע יעיל יותר של חלק מהאלגוריתמים.
טכניקת הקליפרים המסתובבים (rotating calipers) לעיצוב אלגוריתמים גאומטריים ניתנת גם היא לפירוש כצורה של קו סורק – אך במישור הדואלי הפרויקטיבי. במסגרת דואליות פרויקטיבית, השיפוע של קו במישור אחד מומר לקואורדינטת x של נקודה במישור הדואלי. כך, המעבר על קווים בסדר שיפועיהם (כפי שמבצע אלגוריתם הקליפרים המסתובבים) הוא דואלי למעבר על נקודות בסדר ערכי ה־x שלהן (כפי שקורה באלגוריתם קו סורק).
גישת הסחיפה ניתנת להכללה גם לממדים גבוהים יותר.