מוצא את שתי הנקודות הקרובות ביותר במישור דו־ממדי בזמן O(n log n).
שלב 1 מתוך 26
הזוג הקרוב ביותר של נקודות: 11 נקודות. מיין לפי x, ואז הפרד ומשול. אנו מוצאים רקורסיבית את הזוג הקרוב ביותר בחצי השמאלי/ימני, ואז בודקים את הרצועה סמוך לקו החלוקה.
▶אלגוריתם
ClosestPair(P):
sort P by x-coordinate
if |P| ≤ 3: brute-force all pairs
compare each pair, track minimum
mid = median x; divide into left, right
δ_L = ClosestPair(left)
δ_R = ClosestPair(right)
δ = min(δ_L, δ_R)
check strip within ±δ of mid
return min(δ, strip minimum)
מקרא
משווה
הזוג הטוב ביותר
רצועה (±δ)
חלק לפי חציון x. בצע רקורסיה על כל חצי. אחר כך בדוק נקודות בטווח ±δ מקו החלוקה (לכל היותר 8 לכל נקודה). O(n log n) בסך הכול.