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

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

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

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

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

במקרה הפשוט ביותר, המוצג בתמונה הראשונה, נתונה קבוצה סופית של נקודות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{p_1, ..., p_n\}} במישור אוקלידי. במקרה כזה, כל אתר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_k} הוא פשוט נקודה, ותא וורונוי המתאים לו מורכב מכל הנקודות במישור האוקלידי שמרחקן מ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_k} , קטן או שווה למרחקן מכל הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_j} אחר. כל תא כזה מתקבל מהחיתוך של חצאי-מרחבים, ולכן הוא מצולע קמור. המקטעים של דיאגרמת וורונוי הם כל הנקודות במישור שהן שוות-מרחק לשני האתרים הקרובים ביותר אליהן. קודקודי וורונוי (צמתים) הם הנקודות שוות-המרחק לשלושה (או יותר) אתרים.

הגדרה פורמלית

יהי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X} מרחב מטרי עם פונקציית מרחק הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d} . יהי קבוצת אינדקסים ויהי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (P_k)_{k\in{K}}} n-יה סדורה (אוסף מסודר) של תתי-קבוצות לא ריקות (האתרים) של המרחב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X} . תא וורונוי, או אזור וורונוי, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_k} , המשויך עם אתר הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_k} , הוא הקבוצה של כל הנקודות ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X} , שמרחקן מ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_k} אינו גדול יותר ממרחקן לאתרים האחרים , כש-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle j} הוא איזשהו אינדקס השונה מ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} .

במילים אחרות, אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d(x, A) = \inf\{d(x, a)|a\in{A}\}} מסמל את המרחק בין הנקודה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} לתת-הקבוצה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} , אז

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_k = \{x\in{X} |\ d(x, P_k)\leq d(x,P_j) \quad \forall j \neq k\}}

דיאגרמת וורונוי היא פשוט ה-n-יה סדורה של התאים הפענוח נכשל (שגיאת המרה. השרת ("https://en.wikipedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle (R_{k})_{k\in {K}}} .

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

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

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

במרחב האוקלידי הרגיל, אנו יכולים לשכתב את ההגדרה הרשמית במונחים רגילים. כל מצולע וורונוי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_k} משויך לנקודה מחוללת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_k} . יהי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X} קבוצת כל הנקודות במרחב האוקלידי. יהי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_1} הנקודה שמחוללת את אזור וורונוי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_1} , הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_2} הנקודה שמחוללת את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_2} ו- הנקודה שמחוללת את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_3} וכו'. לכן, כמו שביטאו טראן ושות'[3] כל המקומות בתוך מצולע וורונוי, קרובים יותר אל הנקודה המחוללת של אותו מצולע, יותר מאל כל נקודה מחוללת אחרת בדיאגרמת וורונוי במישור האוקלידי.

הדגמה

שגיאה ביצירת תמונה ממוזערת:
דיאגמת וורונוי לפי המרחק האוקלידי
קובץ:Manhattan Voronoi Diagram.svg
דיאגרמת וורונוי לפי מרחק מנהטן

כדוגמה פשוטה, ניקח את המקרה של קבוצת חנויות בעיר. נניח שאנחנו רוצים להעריך את מספר הצרכנים של חנות נתונה. כשכל הפרמטרים האחרים שווים בין החנויות (מחיר, מוצרים, איכות השרות וכו'), זה יהיה הגיוני להניח שהצרכנים יבחרו את החנות המועדפת עליהם פשוט לפי שיקולי מרחק: הם ילכו לחנות הממוקמת הכי קרוב אליהם. במקרה כזה תא וורונוי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_k} של חנות נתונה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_k} יכול לשמש בשביל להעריך בצורה גסה את מספר הצרכנים הפוטנציאלי שילכו לחנות הזו (שמיוצגת על ידי נקודה בעיר שלנו).

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

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\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}}

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

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d[(a_1, a_2), (b_1, b_2)] = |a_1 - b_1| + |a_2 - b_2|}

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

יישומים

ראו גם

קישורים חיצוניים

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

הערות שוליים

  1. ^ Franz Aurenhammer (1991), Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure, ACM Computing Surveys 23(3), 1991, עמ' 345–405
  2. ^ Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000), Spatial Tessellations – Concepts and Applications of Voronoi Diagrams, John Wiley, 2nd edition, 2000, ISBN 0-471-98635-6
  3. ^ Q.T.Tran; D.Tainar; M.Safar (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. עמ' 357. ISBN 9783642037214. 
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0