مخطط فورونوي

في الرياضيات ، مخطط فورونوي هو تقسيم لمستوى إلى مناطق قريبة من كل عنصر من مجموعة معينة من العناصر. ويمكن تصنيفه أيضًا على أنه تبليط . في أبسط الحالات، تكون هذه العناصر عبارة عن عدد محدود من النقاط في المستوى (تُسمى البذور أو المواقع أو المولدات). لكل بذرة منطقة مقابلة ، تُسمى خلية فورونوي ، وتضم جميع نقاط المستوى الأقرب إلى تلك البذرة من أي بذرة أخرى. مخطط فورونوي لمجموعة من النقاط هو ثنائي تثليث ديلاوناي لتلك المجموعة .

سُمّي مخطط فورونوي نسبةً إلى عالم الرياضيات جورجي فورونوي ، ويُعرف أيضاً باسم تجزئة فورونوي ، أو تحليل فورونوي ، أو تقسيم فورونوي ، أو تجزئة ديريشليه (نسبةً إلى بيتر غوستاف ليجون ديريشليه ). تُعرف خلايا فورونوي أيضاً باسم مضلعات ثيسن ^{[ 1 ]} ، نسبةً إلى ألفريد هـ. ثيسن . ^{[ 2 ] [ 3 ] [ 4 ]} لمخططات فورونوي تطبيقات عملية ونظرية في العديد من المجالات، لا سيما في العلوم والتكنولوجيا ، وكذلك في الفنون البصرية . ^{[ 5 ] [ 6 ]}

في أبسط الحالات، كما هو موضح في الصورة الأولى، لدينا مجموعة محدودة من النقاط${\displaystyle \{p_{1},\dots p_{n}\}}$في المستوى الإقليدي . في هذه الحالة، كل نقطة${\displaystyle p_{k}}$يحتوي على خلية مقابلة${\displaystyle R_{k}}$تتكون من النقاط في المستوى الإقليدي التي${\displaystyle p_{k}}$هو أقرب موقع: المسافة إلى${\displaystyle p_{k}}$أقل من أو يساوي الحد الأدنى للمسافة إلى أي موقع آخر${\displaystyle p_{j}}$لموقع آخر${\displaystyle p_{j}}$النقاط الأقرب إلى${\displaystyle p_{k}}$بدلاً من${\displaystyle p_{j}}$تشكل النقاط، أو النقاط المتساوية البعد، نصف فضاء مغلق ، وحدوده هي المنصف العمودي للقطعة المستقيمة${\displaystyle p_{j}p_{k}}$. خلية${\displaystyle R_{k}}$هو نقطة التقاء كل هذه${\displaystyle n-1}$تُعتبر أنصاف فضاءات، وبالتالي فهي مضلع محدب . ^{[ 7 ]} عندما تشترك خليتان في مخطط فورونوي في حدٍّ ما، يكون هذا الحدّ قطعة مستقيمة أو شعاعًا أو خطًا، ويتألف من جميع النقاط في المستوى التي تبعد مسافة متساوية عن أقرب موقعين لهما. رؤوس المخطط، حيث تلتقي ثلاثة حدود أو أكثر، هي النقاط التي لها ثلاثة مواقع أو أكثر من أقرب المواقع التي تبعد مسافة متساوية.

يترك${\textstyle X}$ليكن فضاء متري بدالة مسافة${\textstyle d}$. يترك${\textstyle K}$ليكن مجموعة من المؤشرات ولتكن${\textstyle (P_{k})_{k\in K}}$ليكن مجموعة مرتبة (مجموعة مفهرسة) من مجموعات فرعية غير فارغة (المواقع) في الفضاء${\textstyle X}$خلية فورونوي، أو منطقة فورونوي، ${\textstyle R_{k}}$، المرتبطة بالموقع${\textstyle P_{k}}$هي مجموعة جميع النقاط في${\textstyle X}$المسافة إلى${\textstyle P_{k}}$لا تزيد عن المسافة بينها وبين المواقع الأخرى${\textstyle P_{j}}$، أين${\textstyle j}$هل يوجد أي مؤشر مختلف عن${\textstyle k}$بمعنى آخر، إذا${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$يشير إلى المسافة بين النقطة${\textstyle x}$والمجموعة الفرعية${\textstyle A}$، ثم

$${\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{لكل}}\;j\neq k\}}$$

مخطط فورونوي هو ببساطة مجموعة من الخلايا${\textstyle (R_{k})_{k\in K}}$من حيث المبدأ، يمكن لبعض المواقع أن تتقاطع، بل وتتطابق (يُشرح تطبيق ذلك أدناه للمواقع التي تُمثل المتاجر)، ولكن يُفترض عادةً أنها منفصلة. إضافةً إلى ذلك، يُسمح بوجود عدد لا نهائي من المواقع في التعريف (يُستخدم هذا الإطار في هندسة الأعداد وعلم البلورات )، ولكن مرة أخرى، في كثير من الحالات لا يُؤخذ في الاعتبار سوى عدد محدود من المواقع.

في حالة كون الفضاء فضاءً إقليديًا محدود الأبعاد ، حيث يُمثل كل موقع نقطة، وعدد النقاط محدود، وجميعها مختلفة، فإن خلايا فورونوي تكون متعددات وجوه محدبة ، ويمكن تمثيلها بطريقة تركيبية باستخدام رؤوسها وأضلاعها ووجوهها ثنائية الأبعاد، وما إلى ذلك. يُشار أحيانًا إلى البنية التركيبية الناتجة باسم مخطط فورونوي. مع ذلك، قد لا تكون خلايا فورونوي محدبة أو حتى متصلة.

في الفضاء الإقليدي المعتاد، يمكننا إعادة صياغة التعريف الرسمي بعبارات معتادة. كل مضلع فورونوي${\textstyle R_{k}}$يرتبط بنقطة مولدة ${\textstyle P_{k}}$. يترك${\textstyle X}$ليكن مجموعة جميع النقاط في الفضاء الإقليدي.${\textstyle P_{1}}$كن نقطة تولد منطقة فورونوي الخاصة بها ${\textstyle R_{1}}$،${\textstyle P_{2}}$ذلك يولد ${\textstyle R_{2}}$، و${\textstyle P_{3}}$ذلك يولد ${\textstyle R_{3}}$وهكذا دواليك. ثم، كما عبر تران وآخرون ، ^{[ 8 ]} "جميع المواقع في مضلع فورونوي أقرب إلى نقطة المولد لهذا المضلع من أي نقطة مولد أخرى في مخطط فورونوي في المستوى الإقليدي".

كمثال بسيط، لنفترض وجود مجموعة من المتاجر في مدينة ما. نريد تقدير عدد زبائن متجر معين. مع ثبات جميع العوامل الأخرى (السعر، المنتجات، جودة الخدمة، إلخ)، من المنطقي افتراض أن الزبائن يختارون متجرهم المفضل بناءً على عامل المسافة فقط: سيذهبون إلى المتجر الأقرب إليهم. في هذه الحالة، تُستخدم خلية فورونوي${\displaystyle R_{k}}$متجر معين${\displaystyle P_{k}}$يمكن استخدامها لإعطاء تقدير تقريبي لعدد العملاء المحتملين الذين يذهبون إلى هذا المتجر (والذي يتم تمثيله بنقطة في مدينتنا).

بالنسبة لمعظم المدن، يمكن قياس المسافة بين النقاط باستخدام المسافة الإقليدية المألوفة :

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

أو مسافة مانهاتن :

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

تبدو مخططات فورونوي المقابلة مختلفة باختلاف مقاييس المسافة.

مخططات فورونوي لعشرين نقطة وفقًا لمقياسين مختلفين

المسافة الإقليدية

مسافة مانهاتن

• يتوافق الرسم البياني الثنائي لمخطط فورونوي (في حالة الفضاء الإقليدي ذي المواقع النقطية) مع تثليث ديلاوناي لنفس مجموعة النقاط .
• يجب بالضرورة العثور على أقرب زوج من بين نقاط البداية في خليتين متجاورتين في مخطط فورونوي.
• إذا كان الإعداد هو المستوى الإقليدي وتم إعطاء مجموعة منفصلة من النقاط، فإن نقطتين من المجموعة تكونان متجاورتين على الغلاف المحدب إذا وفقط إذا كانت خلايا فورونوي الخاصة بهما تشترك في جانب طويل لا نهائي.
• إذا كان الفضاء فضاءً معياريًا ، وتم الوصول إلى كل موقع (على سبيل المثال، عندما يكون الموقع مجموعة متراصة أو كرة مغلقة)، فيمكن تمثيل كل خلية فورونوي كاتحاد لقطع مستقيمة تنطلق من المواقع. ^{[ 9 ]} وكما هو موضح هناك، لا تنطبق هذه الخاصية بالضرورة عندما لا يتم الوصول إلى المسافة المطلوبة.
• في ظل شروط عامة نسبيًا (كأن يكون الفضاء محدبًا بانتظام ، وربما لانهائي الأبعاد ، وأن يكون عدد المواقع ذات الشكل العام لانهائيًا، إلخ)، تتمتع خلايا فورونوي بخاصية استقرار معينة: إذ يؤدي تغيير طفيف في أشكال المواقع، كالتغيير الناتج عن إزاحة أو تشويه، إلى تغيير طفيف في شكل خلايا فورونوي. هذا هو الاستقرار الهندسي لمخططات فورونوي. ^{[ 10 ]} وكما هو موضح هناك، لا تنطبق هذه الخاصية بشكل عام، حتى لو كان الفضاء ثنائي الأبعاد (ولكنه غير محدب بانتظام، وبالأخص غير إقليدي) وكانت المواقع عبارة عن نقاط.

يمكن تتبع الاستخدام غير الرسمي لمخططات فورونوي إلى ديكارت في عام 1644. ^{[ 11 ]} استخدم بيتر جوستاف ليجون ديريشليه مخططات فورونوي ثنائية وثلاثية الأبعاد في دراسته للأشكال التربيعية في عام 1850. استخدم الطبيب البريطاني جون سنو مخططًا يشبه مخطط فورونوي في عام 1854 لتوضيح كيف أن غالبية الأشخاص الذين ماتوا في تفشي الكوليرا في شارع برود كانوا يعيشون بالقرب من مضخة شارع برود المصابة أكثر من أي مضخة مياه أخرى.

سُميت مخططات فورونوي نسبةً إلى جورجي فيودوسيفيتش فورونوي الذي عرّف ودرس الحالة العامة ذات الأبعاد n في عام 1908. ^{[ 12 ]} تُسمى مخططات فورونوي المستخدمة في الجيوفيزياء والأرصاد الجوية لتحليل البيانات الموزعة مكانيًا بمضلعات ثيسن نسبةً إلى عالم الأرصاد الجوية الأمريكي ألفريد هـ. ثيسن ، الذي استخدمها لتقدير هطول الأمطار من قياسات متفرقة في عام 1911. ومن الأسماء المكافئة الأخرى لهذا المفهوم (أو حالاته المهمة): متعددات وجوه فورونوي، مضلعات فورونوي، نطاق (نطاقات) التأثير، تحليل فورونوي، تبليط فورونوي، تبليط ديريشليه.

تُنتج عمليات التبليط الفورونوي للشبكات المنتظمة من النقاط في بعدين أو ثلاثة أبعاد العديد من عمليات التبليط المألوفة. وتُعرف الخلايا المقابلة باسم خلايا ويغنر-سيتز .

• تعطي الشبكة ثنائية الأبعاد تبليطًا غير منتظم يشبه قرص العسل، مع سداسيات متساوية ذات تناظر نقطي؛ في حالة الشبكة المثلثية المنتظمة تكون منتظمة؛ في حالة الشبكة المستطيلة تختزل السداسيات إلى مستطيلات في صفوف وأعمدة؛ تعطي الشبكة المربعة تبليطًا منتظمًا للمربعات؛ لاحظ أنه يمكن أيضًا توليد المستطيلات والمربعات بواسطة شبكات أخرى (على سبيل المثال، الشبكة المحددة بواسطة المتجهات (1،0) و(1/2،1/2) تعطي مربعات).
• تُعطي الشبكة المكعبة البسيطة قرص العسل المكعب .
• تعطي الشبكة السداسية المتراصة تبليطًا للفضاء باستخدام أشكال شبه معينية ذات اثني عشر وجهًا .
• تُعطي الشبكة المكعبة ذات المراكز الوجهية تبليطًا للفضاء باستخدام المجسمات الاثني عشرية المعينية .
• تعطي الشبكة المكعبة ذات المركز الجسمي تبليطًا للفضاء باستخدام ثماني السطوح المقطوعة .
• تُعطي المستويات المتوازية ذات الشبكات المثلثية المنتظمة والمحاذية لمراكز بعضها البعض شكل قرص العسل المنشوري السداسي .
• تُعطي بعض الشبكات الرباعية ذات المركز الجسمي تبليطًا للفضاء باستخدام أشكال سداسية معينية ذات اثني عشر وجهًا .

بالنسبة لمجموعة النقاط ( x , y ) حيث x في مجموعة منفصلة X و y في مجموعة منفصلة Y ، نحصل على بلاطات مستطيلة مع النقاط التي ليست بالضرورة في مراكزها. 

على الرغم من أن خلية فورونوي العادية تُعرَّف بأنها مجموعة النقاط الأقرب إلى نقطة واحدة في S ، فإن خلية فورونوي من الرتبة n تُعرَّف بأنها مجموعة النقاط التي لها مجموعة محددة من n نقطة في S كأقرب n جار لها . كما أن مخططات فورونوي ذات الرتب الأعلى تُقسِّم الفضاء.

يمكن توليد مخططات فورونوي ذات الرتبة الأعلى بشكل متكرر. لتوليد مخطط فورونوي من الرتبة n من المجموعة ^S ، ابدأ بالمخطط من الرتبة ( ⁿ − 1 ) واستبدل كل خلية مولدة بواسطة X = { x ₁ , x ₂ , ..., x _{n −1} } بمخطط فورونوي مولد على المجموعة S − X.           

كما هو مُبين في التعريف، يمكن تعريف خلايا فورونوي لمقاييس أخرى غير الإقليدية، مثل مسافة ماهالانوبيس أو مسافة مانهاتن . مع ذلك، في هذه الحالات، قد تكون حدود خلايا فورونوي أكثر تعقيدًا مما هي عليه في الحالة الإقليدية، إذ قد لا يكون الموضع المتساوي البعد لنقطتين فضاءً جزئيًا ذا بُعد مشترك 1، حتى في الحالة ثنائية الأبعاد.

مخطط فورونوي الموزون هو مخطط تُحدد فيه خلية فورونوي بواسطة زوج من النقاط، حيث تكون دالة المسافة مُعدّلة بأوزان ضربية أو جمعية تُخصص لنقاط المولد. على عكس خلايا فورونوي المُحددة باستخدام مسافة قياسية ، قد تكون بعض خلايا فورونوي في هذه الحالة فارغة. مخطط القوة هو نوع من مخططات فورونوي يُحدد من مجموعة دوائر باستخدام مسافة القوة ؛ ويمكن اعتباره أيضًا مخطط فورونوي موزونًا حيث يُضاف وزن مُحدد من نصف قطر كل دائرة إلى مربع المسافة الإقليدية من مركز الدائرة. ^{[ 16 ]}

مخطط فورونوي لـ${\displaystyle n}$النقاط في${\displaystyle d}$يمكن أن يحتوي الفضاء ذو ​​الأبعاد على${\textstyle O(n^{\lceil d/2\rceil })}$تتطلب الرؤوس نفس الحد الأقصى لحجم الذاكرة اللازمة لتخزين وصف صريح لها. لذلك، غالبًا ما تكون مخططات فورونوي غير عملية للأبعاد المتوسطة أو العالية. البديل الأكثر كفاءة في استخدام المساحة هو استخدام مخططات فورونوي التقريبية. ^{[ 17 ]}

ترتبط مخططات فورونوي أيضًا بهياكل هندسية أخرى مثل المحور المتوسط ​​(الذي وجد تطبيقات في تجزئة الصور، والتعرف الضوئي على الأحرف ، وتطبيقات حسابية أخرى)، والهيكل العظمي المستقيم ، ومخططات المناطق .

تُعرف العديد من الخوارزميات الفعّالة لإنشاء مخططات فورونوي، إما مباشرةً (كمخططٍ بحد ذاته) أو بشكل غير مباشر بالبدء بتثليث ديلاوناي ثم الحصول على ثنائيته. تشمل الخوارزميات المباشرة خوارزمية فورتشن ، وهي خوارزمية من رتبة O ( n log( n )) لإنشاء مخطط فورونوي من مجموعة نقاط في مستوى. أما خوارزمية بوير-واتسون ، وهي خوارزمية من رتبة O ( n log( n )) إلى O ( n² ⁾ لإنشاء تثليث ديلاوناي في أي عدد من الأبعاد، فيمكن استخدامها في خوارزمية غير مباشرة لمخطط فورونوي.

بالنسبة لتقريبات الشبكة المنفصلة (مثل عرض البكسل)، تُستخدم خوارزمية فيضان القفز (JFA) ومتغيراتها على نطاق واسع في أجهزة الرسومات التجارية ( وحدات معالجة الرسومات ). وقد طُرحت خوارزمية فيضان القفز القياسية لأول مرة بواسطة رونغ غودونغ في عام 2006، وهي تحسب مخطط فورونوي تقريبيًا في${\displaystyle O(\log N)}$يمر بشكل متوازٍ فوق${\displaystyle N\times N}$الشبكة. ^{[ 43 ] [ 44 ]} تعمل التحسينات اللاحقة، مثل متغير JFA-star العشوائي لعام 2019 الذي قدمه ماكيج أ. تشيزيفسكي، على تحويل تعقيد المرور من التناسب مع دقة الشبكة إلى العدد الإجمالي لنقاط البذور (${\displaystyle n}$، مما يحقق تقاربًا أسرع في حوالي${\displaystyle O(\log ^{*}n)}$يمرر. ^{[ 45 ]}

تستخدم خوارزمية لويد وتعميمها عبر خوارزمية ليند-بوزو-غراي (المعروفة أيضًا باسم تجميع k-means ) إنشاء مخططات فورونوي كإجراء فرعي. تتناوب هذه الطرق بين خطوات يتم فيها إنشاء مخطط فورونوي لمجموعة من النقاط الأولية، وخطوات يتم فيها نقل النقاط الأولية إلى مواقع جديدة أكثر مركزية داخل خلاياها. يمكن استخدام هذه الطرق في فضاءات ذات أبعاد عشوائية للتقارب بشكل تكراري نحو شكل متخصص من مخطط فورونوي، يُسمى تجزئة فورونوي المركزية ، حيث تم نقل المواقع إلى نقاط تمثل أيضًا المراكز الهندسية لخلاياها.

يمكن أيضًا إنشاء شبكات فورونوي ثلاثية الأبعاد.

• 
  نقاط عشوائية في الفضاء ثلاثي الأبعاد لتشكيل تجزئة فورونوي ثلاثية الأبعاد
• 
  شبكة فورونوي ثلاثية الأبعاد مكونة من 25 نقطة عشوائية
• 
  شبكة فورونوي ثلاثية الأبعاد مكونة من 25 نقطة عشوائية بشفافية 0.3 ونقاط
• 
  شبكة فورونوي ثلاثية الأبعاد مكونة من 25 قطعة متعددة السطوح محدبة بنقاط عشوائية

• وايسستين، اريك دبليو “مخطط فورونوي” . عالم الرياضيات .
• مخططات فورونوي في مكتبة خوارزميات الهندسة الحسابية CGAL
• برنامج تجريبي لخوارزمية SFTessellation، التي تُنشئ مخطط فورونوي باستخدام نموذج حريق السهوب