في كل جزء من الألف من الثانية أثناء سيرنا في شوارع المدينة حاملين هواتفنا الذكية، تقوم بروتوكولات الاتصال اللاسلكي بحساب أي محطة قاعدة خلوية توفر أقصر مسار للإشارة، وتُجري عمليات تسليم سلسة (Handovers) عبر حدود إقليمية غير مرئية. وعند ورود مكالمة طوارئ، تقوم أنظمة التوجيه فوراً بتقسيم شبكة الطرق لتحديد أي سيارة إسعاف أو مستشفى يمكنه الوصول إلى المريض في أقل زمن ممكن. وفي الطبيعة — بدءاً من النقوش الشبكية لجلد الزرافة، وتعرق أجنحة اليعسوب، والأعمدة البازلتية السداسية في «ممر العمالقة»، وصولاً إلى الشبكة الكونية للعناقيد المجرية الفائقة المحيطة بالفراغات الكونية العملاقة — تنتظم المادة تلقائياً في فسيفساء مضلعة متشابهة بشكل مذهل.
خلف كل هذه الظواهر في علم الأوبئة المكاني، والتخطيط العمراني، وشبكات الجيل الخامس 5G، وتوليد الشبكات لطريقة العناصر المحدودة (FEM)، وفيزياء الحالة الصلبة، والتشكل الحيوي، تكمن البنية الثنائية الأكثر أصالة في الهندسة الحسابية (Computational Geometry): مخطط فورونوي (Voronoi Diagram) وبيانه الثنائي المستوي تثليث ديلوني (Delaunay Triangulation).
1. وباء الكوليرا في شارع برود بلندن (1854) وولادة الحدود غير المرئية
في أواخر أغسطس 1854، تفشى وباء كوليرا مدمر في حي سوهو (Soho) بوسط لندن حول شارع برود (Broad Street)، مما أودى بحياة أكثر من 500 شخص خلال عشرة أيام (616 إجمالاً). كانت الأوساط الطبية آنذاك تؤمن بـ«نظرية الميازما» (انتقال العدوى عبر الهواء الفاسد)، غير أن الطبيب الرائد جون سنو (Dr. John Snow, 1813–1858) لاحظ أن الأعراض تهاجم الجهاز الهضمي حصرياً، فافترض أن الكوليرا تنتقل عبر مياه الشرب الملوثة.
رسم سنو كل حالة وفاة كعمود أسود على خريطة سوهو وحدد مواقع جميع مضخات المياه العامة. ولدحض المشككين وتفسير نجاة نزلاء إصلاحية الفقراء المجاورة (Workhouse، التي كانت تمتلك بئراً خاصة) وعمال مصنع الجعة (Lion Brewery، الذين كانوا يشربون الجعة مجاناً ولديهم بئر عميقة)، رسم سنو خطاً هندسياً فاصلاً على خريطته: المحل الهندسي للنقاط التي تتساوى عندها مسافة المشي إلى مضخة شارع برود مع مسافة المشي إلى أقرب مضخة مياه عامة بديلة.
flowchart TD
subgraph Soho["سوهو، لندن 1854: التقسيم المكاني حسب الأقرب مسافة"]
P1["مضخة مياه شارع برود<br/>(الموقع المولّد الملوث بالكوليرا p₁)"]
P2["المضخات العامة المحيطة<br/>(المواقع المولّدة السليمة p₂, p₃, ..., pₙ)"]
B["الحد المتساوي البعد / العمود المنصف<br/>d(x, p₁) = min_{j≠1} d(x, pⱼ)"]
C1["خلية فورونوي V(p₁) لشارع برود<br/>(تضم أكثر من 90% من وفيات الكوليرا)"]
C2["خلايا المضخات المجاورة V(pⱼ)<br/>(انخفاض حاد في معدل الوفيات)"]
end
P1 --> B
P2 --> B
B -->|"d(x, p₁) < d(x, pⱼ)"| C1
B -->|"d(x, p₁) > d(x, pⱼ)"| C2
كان هذا المضلع هو خلية فورونوي لمضخة شارع برود، وقد احتوى داخله أكثر من 90% من وفيات الكوليرا! وعندما أُزيل مقبض المضخة في 8 سبتمبر 1854، توقف الوباء فوراً. وقد اكتُشف هذا المفهوم الهندسي مستقلاً عدة مرات: عام 1644 على يد رينيه ديكارت في دواماته الكونية (Principia Philosophiae)، وعام 1850 على يد بيتر غوستاف لوجون ديريكليه (مجالات ديريكليه أو خلايا فيغنر-سايتس في فيزياء البلورات)، وعام 1908 على يد عالم الرياضيات الأوكراني جورجي فورونوي في الفضاء الإقليدي النوني $\mathbb{R}^d$، وعام 1911 على يد عالم الأرصاد ألفريد ثيسن.
2. التعريف الرياضي والتعقيد الخطي لمخطط فورونوي $\text{Vor}(P)$
2.1 تقاطع أنصاف المستويات المغلقة والتحدب
لتكن $P = \{p_1, p_2, \dots, p_n\} \subset \mathbb{R}^2$ ($n \ge 3$) مجموعة منتهية من $n$ نقاط متمايزة (تُسمى المواقع أو المولدات) في المستوي الإقليدي. لأي موقعين متمايزين $p_i, p_j \in P$ ($i \ne j$)، يقسم العمود المنصف $B(p_i, p_j) = \{x \in \mathbb{R}^2 \mid \|x - p_i\|_2 = \|x - p_j\|_2\}$ المستوي إلى نصفي مستويين مغلقين. نصف مستوي الهيمنة $H(p_i, p_j)$ يُعطى بالعلاقة:
$$H(p_i, p_j) = \left\{ x \in \mathbb{R}^2 \;\middle|\; \|x - p_i\|_2 \le \|x - p_j\|_2 \right\} = \left\{ x \in \mathbb{R}^2 \;\middle|\; 2(p_j - p_i)^\top x \le \|p_j\|_2^2 - \|p_i\|_2^2 \right\}$$تُعرَّف خلية فورونوي $\mathcal{V}(p_i)$ المرتبطة بالموقع $p_i$ بأنها تقاطع $n-1$ من أنصاف المستويات المغلقة في مواجهة جميع المواقع الأخرى $p_j$ ($j \ne i$):
$$\mathcal{V}(p_i) = \left\{ x \in \mathbb{R}^2 \;\middle|\; \|x - p_i\|_2 \le \|x - p_j\|_2 \;\;\forall j \ne i \right\} = \bigcap_{j \ne i} H(p_i, p_j)$$بما أن تقاطع المجموعات المحدبة هو مجموعة محدبة دائماً، فإن كل خلية فورونوي إقليدية $\mathcal{V}(p_i)$ هي مضلع محدب. وتكون الخلية $\mathcal{V}(p_i)$ غير محدودة إذا وفقط إذا وقع الموقع $p_i$ على محيط الغلاف المحدب $\text{CH}(P)$.
2.2 إثبات التعقيد الخطي عبر صيغة أويلر: $V \le 2n - 5$ و $E \le 3n - 6$
رغم وجود $\binom{n}{2} = \Theta(n^2)$ زوجاً من المواقع، فإن عدد الرؤوس $V$ وعدد الحواف $E$ لمخطط فورونوي المستوي خطي تماماً بالنسبة إلى $n$. 【البرهان】: نُدمج المستوي $\mathbb{R}^2$ على الكرة الطوبولوجية $\mathbb{S}^2$ بإضافة رأس عند اللانهاية $v_\infty$ تتصل به جميع أشعة فورونوي غير المحدودة. نحصل على بيان مستوٍ متصل $G' = (V', E', F')$ عدد رؤوسه $V' = V + 1$، وعدد حوافه $E' = E$، وعدد وجوهه $F' = n$. بتطبيق صيغة أويلر $V' - E' + F' = 2$:
$$(V + 1) - E + n = 2 \iff E = V + n - 1$$وبما أن كل رأس فورونوي منتهٍ وكذلك $v_\infty$ هو نقطة التقاء 3 خلايا على الأقل، فإن درجة كل رأس من الرؤوس $V + 1$ تحقق $\deg(v) \ge 3$. ومن توطئة المصافحة (Handshaking Lemma):
$$2E = \sum_{v \in V \cup \{v_\infty\}} \deg(v) \ge 3(V + 1) \implies V \le \frac{2}{3}E - 1$$بالتعويض في $E = V + n - 1$ نجد $E \le 3n - 6$ و $V \le 2n - 5$. ولأن كل حافة تفصل بين خليتين بالضبط، فإن متوسط عدد الحواف لكل خلية فورونوي هو:
$$\bar{k} = \frac{2E}{n} \le \frac{2(3n - 6)}{n} = 6 - \frac{12}{n} < 6$$أياً كان عدد ملايين النقاط في المستوي، فإن متوسط عدد أضلاع خلية فورونوي أقل دائماً وبصرامة من 6 أضلاع!
| نوع مخطط فورونوي | دالة المسافة $d(x, p_i)$ | هندسة المنصفات | التحدب والطوبولوجيا | الحجم في أسوأ حالة | التطبيقات العلمية والهندسية |
|---|---|---|---|---|---|
| الإقليدي القياسي ($L_2$) | $\|x - p_i\|_2$ | خط مستقيم (عمود منصف) | محدب ومتصل دائماً | $\Theta(n)$ | طوارئ المستشفيات، الأرصاد الجوية (ثيسن)، البحث عن الأقرب |
| مانهاتن ($L_1$) | $\|x_1 - x_i\| + \|x_2 - y_i\|$ | خط منكسر أفقي ورأسي وبزاوية $\pm 45^\circ$ | نجمي (غير محدب بالضرورة) | $\Theta(n)$ | لوجستيات المدن الشبكية، تصميم رقائق VLSI |
| تشيبيشيف ($L_\infty$) | $\max(\|x_1 - x_i\|, \|x_2 - y_i\|)$ | خط منكسر أفقي ورأسي وبزاوية $\pm 45^\circ$ | نجمي | $\Theta(n)$ | رافعات المستودعات الآلية، تخطيط مسار الروبوتات |
| الموزون جمعياً (AW) | $\|x - p_i\|_2 - w_i$ | أقواس قطع زائد | نجمي ومتصل | $\Theta(n)$ | نمو البلورات غير المتزامن (جونسون-ميل)، تحديد المواقع TDOA |
| الموزون ضربياً (أبولونيوس) | $\|x - p_i\|_2 / w_i$ | أقواس دائرية (دوائر أبولونيوس) | غير محدب، قد ينفصل | $\Theta(n^2)$ | خلايا 5G بقدرات بث متفاوتة، مناطق الجذب التجاري |
| مخطط القوة (لاغير / Power) | $\|x - p_i\|_2^2 - r_i^2$ | خط مستقيم (المحور الجذري لدائرتين) | محدب دائماً (قد يكون فارغاً) | $\Theta(n)$ | المعادن متعددة البلورات، فيزياء الرغوة، النقل الأمثل (OT) |
3. البيان الثنائي: تثليث ديلوني $\text{DT}(P)$ ونظريات التكافؤ الثلاث
في عام 1934، عرّف عالم الرياضيات الروسي بوريس ديلوني (Boris Delaunay / Delone) البيان الثنائي المستوي لمخطط $\text{Vor}(P)$ بوصل كل موقعين $p_i, p_j \in P$ بقطعة مستقيمة إذا وفقط إذا اشتركت خليتاهما $\mathcal{V}(p_i)$ و $\mathcal{V}(p_j)$ في حافة فورونوي. في الوضع العام، ينتج عن ذلك تثليث ديلوني $\text{DT}(P)$ الذي يتميز بثلاث نظريات متكافئة:
- خاصية الدائرة المحيطة الفارغة (Empty Circumcircle Property): يكون التثليث $\mathcal{T}$ تثليث ديلوني إذا وفقط إذا كانت الدائرة المحيطة $C(\triangle p_i p_j p_k)$ بكل مثلث خالية تماماً في داخلها الصريح من أي موقع آخر $p_l \in P$ (لأن مركز الدائرة المحيطة هو رأس فورونوي الثنائي). ويُختبر ذلك جبرياً عبر محدد $4 \times 4$: $\text{InCircle}(p_i, p_j, p_k, p_l) > 0$.
- أمثلية تعظيم الزاوية الصغرى (Max-Min Angle Optimality — سيبسون 1978 وقلب الحواف للوسون 1972): في طريقة العناصر المحدودة (FEM)، تؤدي المثلثات الإبرية المسطحة (sliver triangles) إلى تدهور عدد الشرط لمصفوفة الصلابة $\kappa(K) \propto 1/\sin(\theta_{\min})$. ومن بين جميع التثليثات الممكنة للمجموعة $P$، يعظم $\text{DT}(P)$ معجمياً متجه الزوايا الداخلية المرتب تصاعدياً $\alpha(\mathcal{T})$، وبوجه خاص يعظم أصغر زاوية داخلية $\theta_{\min}$! وتتقارب خوارزمية قلب الحواف للوسون (Edge Flip) إلى $\text{DT}(P)$ في $O(n^2)$ خطوة على الأكثر.
- الرفع إلى المجسم المكافئ ثلاثي الأبعاد (Edelsbrunner & Seidel 1986): عند إسقاط كل نقطة ثنائية الأبعاد $(x, y)$ عمودياً على المجسم المكافئ الدوراني $\mathcal{P}: z = x^2 + y^2$ في $\mathbb{R}^3$ عبر التطبيق $\Phi(x, y) = (x, y, x^2 + y^2)$، تتحول معادلة الدائرة $(x-a)^2 + (y-b)^2 = R^2$ إلى معادلة مستوٍ خطي ثلاثي الأبعاد $z = 2ax + 2by - (a^2 + b^2 - R^2)$. وبالتالي، فإن تثليث ديلوني $\text{DT}(P)$ هو بالضبط المسقط العمودي على المستوي $xy$ للغلاف المحدب السفلي (Lower Convex Hull) لمجموعة النقاط المرفوعة $\Phi(P)$ في $\mathbb{R}^3$!
4. خوارزمية خط المسح و«خط الشاطئ» لستيفن فورتشن (1986) في زمن $\Theta(n \log n)$
يفشل المسح المستوي الساذج لأن نقطة فوق خط المسح $\ell: y = y_{\text{sweep}}$ قد تكون أقرب إلى موقع لم يُكتشف بعد تحت $\ell$. وفي عام 1986، حلّ ستيفن فورتشن (Steven Fortune) هذه المفارقة عبر صيانة خط الشاطئ (Beach Line)، وهو الغلاف السفلي للقطوع المكافئة التي بؤرها المواقع التي تمت زيارتها $p_i = (x_i, y_i)$ ($y_i > y_{\text{sweep}}$) ودليلها خط المسح $\ell$:
$$y = \frac{(x - x_i)^2}{2(y_i - y_{\text{sweep}})} + \frac{y_i + y_{\text{sweep}}}{2}$$إن نقاط الانكسار (breakpoints) بين قوسين متجاورين متساوية البعد عن البؤرتين والدليل معاً، ولذلك ترسم بدقة حواف فورونوي أثناء هبوط $\ell$! وباستخدام شجرة بحث ثنائية متوازنة (تحوي على الأكثر $2n-1$ قوساً) ورتل أولويات لمعالجة $n$ من أحداث المواقع (Site Events) وعلى الأكثر $2n-5$ من أحداث الدوائر (Circle Events — تلاشي قوس عند أدنى نقطة لدائرة محيطة $y_{\text{sweep}} = y_c - R$ مولداً رأس فورونوي)، تحقق الخوارزمية الزمن الأمثل $\Theta(n \log n)$ والمساحة $\Theta(n)$.
5. استرخاء لويد وتبليطات فورونوي المركزية (CVT)
لتقليل طاقة التكميم المكاني (دالي $k$-Means) الموزونة بكثافة $\rho(x)$:
$$\mathcal{E}(P, \{\Omega_i\}) = \sum_{i=1}^n \int_{\Omega_i} \|x - p_i\|_2^2 \, \rho(x) \, dx$$يجب أن تكون المناطق $\Omega_i$ هي خلايا فورونوي $\mathcal{V}(p_i)$، وأن ينطبق كل مولد $p_i$ على مركز ثقل (Centroid) خليته $c_i$ ($p_i = c_i$)، مما يشكل تبليط فورونوي المركزي (CVT). وتعمل خوارزمية لويد (Stuart Lloyd, 1957) على تحريك كل موقع تكرارياً إلى مركز ثقل خليته ($p_i^{(t+1)} \leftarrow c_i^{(t)}$)، مما يخفض الطاقة $\mathcal{E}$ بشكل رتيب نحو شبكة سداسية منتظمة كخلية النحل (مبرهنة فيجيس توث، 1953).
فيما يلي تطبيق برمجي متكامل بلغة Python لقص أنصاف المستويات بطريقة ساذرلاند-هودجمان، وحساب المساحة ومركز الثقل والطاقة عبر مبرهنة غرين، واسترخاء لويد:
| |