שילוש דלוני
שילוש דלוני (או תילות דלוני) מחלק את המישור למשולשים כך שכל נקודה היא קודקוד של משולש. המשמעות החשובה היא: אין נקודה שנמצאת בתוך המעגל שעובר דרך שלושת קודקודי משולש. (מעגל שעובר דרך כל שלושת הקודקודים זה מעגל חוסם.) בשילוש כזה המשולשים בדרך כלל עבים ולא דקים. = הגדרה פורמלית = יש כמה דרכים שוות להג...
אלגוריתם הפרד ומשול
הפרד ומשול היא דרך לפתור בעיות על ידי חלוקה לחלקים קטנים יותר. כל חלק הוא בעיה דומה. אחרי שמפתרים את כל החלקים, מחברים את התשובות ביחד. אומרים שהדרך היא רקורסיה. רקורסיה זו קריאה של פונקציה לעצמה. אפשר גם לעשות את זה בלי רקורסיה, בעזרת מחסנית (מבנה שמאחסן דברים לפי סדר). השיטה טובה לבעיות קשות. אם...
מיון מיזוג
מיון מיזוג הוא דרך למיין רשימה של דברים בסדר עולה. המציא את השיטה ג'ון פון נוימן ב-1945. מעבירים את הרשימה לחלקים קטנים עד שכל חלק יש בו פריט אחד. פריט אחד כבר ממויין. כדי לחבר שני חלקים ממוינים, בוחנים את הפריט הראשון בכל חלק. לוקחים את הפריט הקטן יותר ומכניסים אותו לרשימה החדשה. חוזרים כך עד ש...
מיון מהיר
מיון מהיר (Quicksort) מסדר רשימות מהר. המציא אותו טוני הואר ב־1959, 1961. ראשית בוחרים מספר מהרשימה והופכים אותו ל"איבר ציר". זהו המספר שמשווים אליו. אחרי זה מפרידים את הרשימה לשתי קבוצות: מספרים קטנים או שווים לציר, ומספרים גדולים מהציר. חוזרים על הפעולה על כל קבוצה עד שכל קבוצה קטנה מאוד. כך בסוף...
עץ kd
עץ kd הוא מבנה נתונים שמאחסן נקודות במרחב. נקודה היא מקום עם מספרים שמגלים איפה היא. בדוגמה של שני ממדים, יש לכל נקודה x ו-y. בשורש העץ חוצים את המישור בקו אנכי לפי x. נקודות מימין הולכות לצד ימין, ונקודות משמאל הולכות לצד שמאל. בשכבה הבאה חוצים בקו אופקי לפי y. החיתוכים מתחלפים בכל רמה. בממדים אח...