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

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

במקרה הפשוט ביותר, המוצג בתמונה הראשונה, נתונה קבוצה סופית של נקודות ${\displaystyle \{p_{1},...,p_{n}\}}$ במישור אוקלידי. במקרה כזה, כל אתר ${\displaystyle p_{k}}$ הוא פשוט נקודה, ותא וורונוי המתאים לו ${\displaystyle R_{k}}$ מורכב מכל הנקודות במישור האוקלידי שמרחקן מ-${\displaystyle p_{k}}$, קטן או שווה למרחקן מכל ${\displaystyle p_{j}}$ אחר. כל תא כזה מתקבל מהחיתוך של חצאי-מרחבים, ולכן הוא מצולע קמור. המקטעים של דיאגרמת וורונוי הם כל הנקודות במישור שהן שוות-מרחק לשני האתרים הקרובים ביותר אליהן. קודקודי וורונוי (צמתים) הם הנקודות שוות-המרחק לשלושה (או יותר) אתרים.

יהי ${\displaystyle X}$ מרחב מטרי עם פונקציית מרחק ${\displaystyle d}$. יהי ${\displaystyle K}$ קבוצת אינדקסים ויהי ${\displaystyle (P_{k})_{k\in {K}}}$ n-יה סדורה (אוסף מסודר) של תתי-קבוצות לא ריקות (האתרים) של המרחב ${\displaystyle X}$. תא וורונוי, או אזור וורונוי, ${\displaystyle R_{k}}$, המשויך עם אתר ${\displaystyle P_{k}}$, הוא הקבוצה של כל הנקודות ב-${\displaystyle X}$, שמרחקן מ-${\displaystyle P_{k}}$ אינו גדול יותר ממרחקן לאתרים האחרים ${\displaystyle P_{j}}$, כש-${\displaystyle j}$ הוא איזשהו אינדקס השונה מ-${\displaystyle k}$.

במילים אחרות, אם ${\displaystyle d(x,A)=\inf\{d(x,a)|a\in {A}\}}$ מסמל את המרחק בין הנקודה ${\displaystyle x}$ לתת-הקבוצה ${\displaystyle A}$, אז

${\displaystyle R_{k}=\{x\in {X}|\ d(x,P_{k})\leq d(x,P_{j})\quad \forall j\neq k\}}$

דיאגרמת וורונוי היא פשוט ה-n-יה סדורה של התאים ${\displaystyle (R_{k})_{k\in {K}}}$.

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

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

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

במרחב האוקלידי הרגיל, אנו יכולים לשכתב את ההגדרה הרשמית במונחים רגילים. כל מצולע וורונוי ${\displaystyle R_{k}}$ משויך לנקודה מחוללת ${\displaystyle P_{k}}$. יהי ${\displaystyle X}$ קבוצת כל הנקודות במרחב האוקלידי. יהי ${\displaystyle P_{1}}$ הנקודה שמחוללת את אזור וורונוי ${\displaystyle R_{1}}$, ${\displaystyle P_{2}}$ הנקודה שמחוללת את ${\displaystyle R_{2}}$ ו-${\displaystyle P_{3}}$ הנקודה שמחוללת את ${\displaystyle R_{3}}$ וכו'. לכן, כמו שביטאו טראן ושות'^[3] כל המקומות בתוך מצולע וורונוי, קרובים יותר אל הנקודה המחוללת של אותו מצולע, יותר מאל כל נקודה מחוללת אחרת בדיאגרמת וורונוי במישור האוקלידי.

כדוגמה פשוטה, ניקח את המקרה של קבוצת חנויות בעיר. נניח שאנחנו רוצים להעריך את מספר הצרכנים של חנות נתונה. כשכל הפרמטרים האחרים שווים בין החנויות (מחיר, מוצרים, איכות השרות וכו'), זה יהיה הגיוני להניח שהצרכנים יבחרו את החנות המועדפת עליהם פשוט לפי שיקולי מרחק: הם ילכו לחנות הממוקמת הכי קרוב אליהם. במקרה כזה תא וורונוי ${\displaystyle R_{k}}$ של חנות נתונה ${\displaystyle P_{k}}$ יכול לשמש בשביל להעריך בצורה גסה את מספר הצרכנים הפוטנציאלי שילכו לחנות הזו (שמיוצגת על ידי נקודה בעיר שלנו).

עבור רוב הערים, המרחק בין הנקודות יכול להימדד באמצעות המרחק האוקלידי המוכר:

${\displaystyle l_{2}=d\left[(a_{1},a_{2}),(b_{1},b_{2})\right]={\sqrt {(a_{1}-b_{1})^{2}+(a_{2}-b_{2})^{2}}}}$

או מרחק מנהטן:

${\displaystyle d[(a_{1},a_{2}),(b_{1},b_{2})]=|a_{1}-b_{1}|+|a_{2}-b_{2}|}$

דיאגרמות וורונוי המתאימות לכל מטריקת מרחק, שונות אחת מהשנייה.

• שילוש דלוני - מבנה דואלי לדיאגרמת וורוני

מדיה וקבצים בנושא דיאגרמת וורונוי בוויקישיתוף

• דיאגרמת וורונוי, באתר MathWorld (באנגלית)