רעיון שהיה לי עוד קודם היה:
נמיין הנקודות בX ובY ונסדר אותם במטריצה דיסקרטית, כך שבכל
שורה ועמודה יש נקודה בודדת.(לצורך פשטות נניח
כי כל ערכי X ו Y שונים), וכן נשמור בכל שורה ועמודה
מי היא הנקודה באותה שורה/עמודה(למעשה לא צריך מטריצה,
זה כלי מחשבתי שעזר לי)
אז נרצה לנסות עבור כל נקודה למצוא את הנקודה הקרובה ביותר
(שזה יותר מהנדרש במקור),אנו נחפש ימינה שמאלה מעלה ולמטה,
כל פעם לכיוון בו הלכנו עד כה הכי פחות(מבחינת מרחק "אמיתי"
ולא מהחינת מספר שורות/עמודות, יש מעברי שורה שמייצגים
פער מרחק גדול ויש שקטן), אם התרחקנו בX או בY יותר מהמרחק
המינמלי שמצאנו עד כה, אפשר להפסיק להתקדם בכיוון.
קל לראות, שיש נקודות שיקח O(N) זמן למצוא עבורם הנקודה הקרובה
ביותר, השאלה היא האם יש הרבה נקודות כאלו. אני מאמין שלא.
ניתוח סיבוכיות מדויק, כמה זמן העסק לוקח עבור כל הנקודות אין
לי.

הפתרון הוא דיאגרמת ורוני (VORONOI) : הנה PDF מצוין שמסביר מהו מבנה הנתונים
http://graphics.lcs.mit.edu/classes/6.838/F01/lectures/Voronoi/Voronoi2D.pdf

זמן הבניה של הדיאגרמה הוא O של NLOGN .מספר הצלעות בדיאגרמה הוא O של N(למעשה חסום על ידי 3N-6).
כל צלע - מרחקה שווה משתי הנקודות בינהם אהיא נמצאת .
נחשב לכל צלע המרחק הנ"ל - ונמצא המינימום .. (השלב הזה לוקח O של N).

אני מצאתי כמה דברים על בסיס עצי KD אבל בכולם התחבא איזה
משהוא היוריסטי. אם בונים עץ KD, אפשר להריץ עליו חיפוש A*
ולמצוא נקודה שקרובה לנקודה כלשהיא בזמן שהוא סביר להניח log(N)
אני חושב שלצורך השאלה באשכול זה, פתרון על בסיס כזה עשוי
דווקא לצאת n*log(N) גם במקרה הגרוע ביותר, אבל משום שהפתרון
שהבאת(על אף שהוא מורכב בהרבה) הוא בפרוש נכון, לא אתעמק בזה.

DRYICE

אם אני מסתכל על OCR פשוט, אני רוצה לסווג אות בכתב יד,
ואני לוקח תמונה של האות בגודל 8X8 יש פה 64 מימדים.

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

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