مخطط فورونوي

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

النقاط التي لا تبعد عن نقطة مولّدة $p$ أكثر مما تبعد عن نقطة أخرى $q$ تشكّل نصف مستوى يحدّه المنصف العمودي للقطعة $pq$. منطقة $p$ هي تقاطع أنصاف المستويات هذه، واحد لكل نقطة مولّدة أخرى، لذا فهي محدّبة. لا يتحوّل إلى حواف إلا بعض هذه المنصفات. النقاط المولّدة التي تشترك مناطقها في حافة مع منطقة $p$ هي جيرانها؛ أما أنصاف المستويات الأخرى فتحتوي المنطقة كاملة أصلًا. الإطار يحدّ النافذة فقط. وتمتد المنطقة إلى ما لا نهاية إذا وفقط إذا كانت نقطتها المولّدة على حدّ الغلاف المحدّب لجميع النقاط المولّدة.

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

يُنمّي نمو قرصًا من كل نقطة مولّدة بالسرعة نفسها. تصل جبهة أقرب نقطة مولّدة إلى كل موضع أولًا، فتلتقي الجبهات على الحواف تمامًا. يعرض المنظر الصغير النمو نفسه من الجانب. فوق كل موضع، يجعل الارتفاع مساويًا للمسافة إلى أقرب نقطة مولّدة: أدنى ارتفاع بين المخاريط $z = |x - s|$ القائمة على النقاط. خطوط القمم هي حواف المناطق، والنمو هو ارتفاع الماء. آخر مكان يغمره الماء هو أعلى نقطة من التضاريس داخل الإطار، ومركز أكبر دائرة خالية يقع مركزها داخل الإطار.

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

ينقل توزيع متساوٍ كل نقطة مولّدة إلى مركز ثقل منطقتها بعد قصّها بالإطار، ثم يعيد إنشاء المناطق، جولة بعد جولة. هذه خوارزمية لويد. يرسم العرض الصغير متوسط مربع المسافة من نقطة داخل الإطار إلى أقرب نقطة مولّدة، مقسومًا على مساحة الإطار لكل نقطة مولّدة. لا تستطيع أي جولة زيادة هذه القيمة. عند تثبيت النقاط، تجعلها مناطق أقرب نقطة أصغر ما يمكن؛ وعند تثبيت المناطق، تفعل مراكز الثقل ذلك. خط قرص العسل حدّ أدنى: قيمة السداسيات المنتظمة المتساوية، مع النقاط المولّدة في مراكزها. انطلاقًا من نقاط متناثرة، تتوقف العملية عند حالة مستقرة قريبة، لا عند قرص عسل مثالي. عادةً تبقى خماسيات وسباعيات متجاورة، مثل الانخلاعات في البلّورات.

سُمّي المخطط باسم غيورغي فورونوي، الذي درس هذه التقسيمات في أي عدد من الأبعاد عام ⁦1908⁩، وسُمّي التثليث باسم بوريس ديلوني، الذي وصفه عام ⁦1934⁩.