דיאגרמת וורונוי

20 נקודות ותאי הוורונוי שלהן

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

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

המקרה הפשוט ביותר

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

הגדרה רשמית

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

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

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

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

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

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

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

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

הערות שוליים

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