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

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

בוא ניזכר בחידה ונפתור
קלט:
אוסף של n נק' במישור xy.
פלט:
המרחק הקצר ביותר בין 2 נקודות.

הגישה הנאיבית לעבור על כל זוגות הנק' עולה לנו O של n^2.
אני אתאר גישה אחת של הפרד ומשול ואתן רעיונות לגישות נוספות.

פתרון מלא בעזרת אלגוריתם הפרד ומשול:
1. נמיין את מערך הנק' עפ"י קורדינטת ה-X שלהם.
2. נפתור את הבעייה באופן רקורסיבי לשני חצאי המישור, כלומר נחלק את המישור בכל שלב ל-2 חלקים עם מספר שווה של נק' ונשאל מה המרחק המינימלי בכל צד. נסמן Lmin ו-Rmin בהתאמה עבור המרחק המינימלי של צד שמאל וימין.
[ תנאי העצירה הוא כמובן ברגע שיש לנו 2 נק' נחזיר את המרחק ביניהן ]
מה חסר?
הבעייה היא בכך שאי אפשר לומר שהמרחק המינימלי יהיה המינימום מבין Rmin ל-Lmin (הקטנים ביותר), מכיוון שברגע שאנחנו מחלקים את המישור לשני חצאים ייתכן שיהיה זוג נק' עם מרחק קטן יותר שכל אחת מהנק' שייכת לחצי אחר.

באדום ובכחול מסומן המרחק המינימלי בעוד שהמרחק המינימלי האמיתי הוא הסגמנט הסגול.
עומר בזמנו הגיע עד פה והציע כדי לפתור את הבעייה לבדוק את המרחק מהחציון לכל הנק' בכל שלב כדי לפתור את הבעייה. אולם אין זה נכון פשוט. אפשר לראות בציו שהמרחק המינימלי בכלל לא קשור במקרה זה לחציון.
אז מה כן אפשר לעשות
המטרה שלנו היא למצוא את המרחק המינימלי גם בין כל הנק' בצד שמאל לכל הנק' בצד ימין. אם נעבור שוב על כל הנק' בצד שמאל עם כל הנק' בצד ימין אז זה עדיין מקפיץ את הפתרון לריבועי. יתרה מזאת, אנחנו רוצים בכל איטרציה שזה ייקח לכל היותר n (עומק הרקורסיה הוא log n, ולכן O של n זה הגבול שנוכל לדרוש לצעד הזה).
מי שעקב עד לפה, מוזמן לחשוב לרגע כיצד לפתור את זה לפני שהוא קורא את ההסבר.
אז מה באמת נעשה?
אנחנו יודעים את המרחק Lmin ו-Rmin ויכולים להעזר במידע הזה. נסמן ב-d את המינימום מבין Rmin ו-Lmin. אז קודם כל נסתכל על החציון ונסתכל על המלבן האינסופי שנוצר מהסתכלות על mid+d ו-mid-d, כלומר:

זה האיזור ה"מסוכן" - נק' משני הצדדים במרחק קטן מ-d עלולות להמצא רק בקטע זה. ניקח נק' נק' בצד שמאל ונקיף סביב כל נק' רדיוס באורך d. כמה נקודות מצד ימין המעגל הזה יכול להכיל? זה דורש מחשבה קלה.
נסתכל על המעגל:

חילקתי אותו גם עם קוטר לשני חלקים. החלק הימיני של המישור מוכל בחצי מעגל הימיני. ניעזר בעובדה (שקל לראות) שכל 3 נק' שנבחר על המעגל יהיו באיזשהו חצי מעגל, ולכן אם נוסיף נק' 4 נקבל כבר זוג נק' מצד ימין שהמרחק ביניהם קטן מרדיוס המעגל, אבל רדיוס המעגל קטן מ-Lmin וזה לא הגיוני.
המחשה עבור נק' מצד ימין:

(נסו לצייר בעצמכם 4 נק' של צד ימין במעגל ותבינו איפה אתם נופלים).
לסיכום:
כאשר נעבור על כל נק' בצד שמאל ונעשה סביבם מעגל ברדיוס קטן כזה, יהיו לכל היותר 3 נק' מצד ימין. נותר לנו אם כן עבור כל מעגל כזה לבדוק את ה-3 נק' שהוא מכיל לכל היותר מצד מימין ולבדוק אותן. גם זה מתעתע, כי זה לא כזה פשוט למצוא את 3 הנק' האלה. אפשר למיין למשל את הסגמנט של כל הערכים עם ערך X פוטנציאלי (להיות ב-mid+d ו-mid-d) לפי קורדינטת ה-Y ואז לעבור באופן סדרתי על הנק' ולבדוק הימצאותן במעגלים. זה יעלה לנו nlog n.
כלומר באופן זה אני פותר את הבעייה ב-nlog ^2 n שזה כבר טוב יותר.
הערה אחרונה:
יכולנו לחסוך את העלות הזאת לו בכל איטרציה היינו ממיינים רקורסיבית את הערכים לפי ציר Y וממזגים את הערכים המתאימים במלבן בבואנו לבדוק את הנק' שנמצאות בתוך המעגלים - זה היה עולה לנו רק n, וכך היה נפתר האלגוריתם ב-nlog n.

לסיכום אלגוריתם הפרד ומשול:
1. חלק את אוסף הנק' ל-2 חלקים עם כמות שווה של נק'.
2. מצא בכל חלק את המרחק המינימלי.
3. מצא את הנק' ששוכבות במלבן mid+d ו-mid-d באשר d המרחק המינימלי מבין המרחק המינימלי בחצי מישור שמאלי וחצי מישור ימיני.
4. מתח מעגלים סביב כל נק' מצד שמאל הנמצאת במלבן האינסופי ובדוק אותה מול 3 הנק' שפוטנציאליות להיות בתוכה.
5. החזר את הערך המינימלי מבין Lmin, Rmin, Dmin.
עלות כוללת:
nlg ^2 n
ואם עובדים חכם יותר:
nlg n

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

גישות נוספות:
1. דיאגרמת Voronoi - כלי עצמתי יחסית. פותר בעייה גדולה יותר - בהנתן אוסף של אתרים מחזיר גרף המפריד את הנק' לאיזורי שליטה מהבחינה הזאת שאיזור השליטה של נק' p, נסמן Vp, מכיל את המקום הגיאומטרי של כל הנק' הקרובות ל-p לפחות כפי שהן קרובות לשאר האתרים. אפשר לחשוב על האתרים כבתי חולים ועל הגרף כחלוקה לאיזורים Vp כך שאם אדם נמצא באיזור Vp אז בית החולים הקרוב ביותר אליו הוא לכל הפחות p.
http://www-sop.inria.fr/prisme/fiches/Voronoi/voronoi.gif
אפשר לבנות גרף כזה ב-nlog n. מספר הקשתות שלו הוא O של n, ולכן אפשר פשוט להחזיר את המינימום מבין כל הקשתות (שאינן אינסופיות).
2. אלגוריתם של Sweep. גישה מאוד אלגנטית לפתרון בעיות בגיאומטריה חישובית. היא למעשה ממחישה כיצד לדמות סריקה רציפה של תחום בעזרת מעבר בדיד על הנקודות.