خوارزمية الهيكل المحدب

الهيكل المحدب لمجموعة من النقاط

تستخدم الخوارزميات التي تبني هياكلاً محدبة في مجالات الرياضيات وعلوم الحاسوب.

في الهندسة الحسابية، اقترح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من تعقيد العمليات الحسابية.

تمثل خوارزمية الهيكل المحدب الشكل المطلوب لبناء الهيكل بطريقة فعالة وواضحة ومن الممكن تقدير تعقيد هذه الخوارزميات ب n والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. أو من الممكن تقديرها ب h والتي تمثل عدد النقاط على حدود الهيكل المحدب.

الحالة المستوية لبناء الهيكل المحدب

في البداية لنعتبر أن الحالة العامة لبناء الهيكل المحدب تكون مدخلاتها عبارة عن مجموعة محددة غير مرتبة من النقاط على مستوى ديكارت. وهناك حالة خاصة للمدخلات سيأتي فيما بعد توضيحها بحيث تكون فيها النقاط المدخلة مرتبة على حدود مضلع بسيط.

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

الحد الأدنى من التعقيد الحسابي

إن معرفة التعقيد الحسابي لبناء الهيكل المحدب المضلع لمجموعة من النقاط في فضاء ثنائي الابعاد، يتم تمثيله بسهولة وذلك لامتلاكه نفس التعقيد الحسابي الموجود في خوارزمية ترتيب النقاط، باستخدام الإسقاط التالي: لكل مجموعة من الارقام  المراد ترتيبها ${\displaystyle x_{1},\dots ,x_{n}}$ نقوم بإنشاء النقاط التالية في فضاء ثنائي الابعاد ${\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}$

ولأن كل نقطة من هذه النقاط تقع على القطع المكافئ والذي يعد بطبيعته منحنى محدب فانه من السهل ايجاد النقاط التي شكلت الهيكل المحدب حيث تكون على طول حدود القطع المكافئ، والتي يمكن الحصول عليها من خلال ترتيب الأرقام ${\displaystyle x_{1},\dots ,x_{n}}$ . ومن الواضح ان عملية تحويل الارقام لنقاط تستهلك وقتا يمكن تمثيله بمنحنى خطي، وهذا يؤكد على عدم امكانية حساب الهيكل المحدب لمجموعة من النقاط في الحالة العامة بوقت اسرع من وقت ترتيب مجموعة من الأرقام.

إن نموذج شجرة القرار مستخدم في اثبات أن الحد الادنى من التعقيد الحسابي المطلوب لترتيب مجموعة من الأرقام هو Ω (n log n). ويجب التنويه هنا إلى أن هذا التعقيد الحسابي مرتبط فقط بعمليات المقارنة وليس بالعمليات الحسابية المستخدمة في ترتيب هذه الأرقام. ولكن لا يمكن أبدا استخدام هذه الطريقة لحساب الهياكل المحدبة. ولذلك فان الطريقة الأكثر ملائمة لحساب الهيكل المحدب بنفس التعقيد الحسابي هي شجرة القرار الجبري.^[1]

و نتيجة لأن نماذج حسابات الكمبيوتر التي تسمح بترتيب مجموعة من الارقام في وقت حسابي اسرع من O(n log n)، مثل استخدام خوارزمية ترتيب الاعداد الصحيحة،  فإن حساب الهياكل المحدبة المستوية يمكن ايجادها بطريقة أسرع: كخوارزمية جرهام للبحث المكونة من عملية ترتيب واحدة متبوعة بعمل إضافي يمكن تمثيله بوقت حسابي خطي.

الخوارزميات المعتمدة على المخرجات

يمكن تصنيف التعقيد الحسابي لبناء الهيكل المحدب بناءً على: عدد النقاط المدخلة - والتي ذكرنا سابقاً أن الحد الأدنى لتعقيدها الحسابي يمكن حصره ب (Ω (n log n - أو على عدد النقاط التي ستشكل الهيكل المحدب (h) ويمكن تسميتها ب بالخوارزميات المعتمدة على المخرجات والتي تستهلك تعقيد حسابي أكثر فاعلية من Θ (n log n) في حال كان h=o(n).

ان الحد الأدنى للتعقيد الزمني في أسوأ حالة لخوارزميات الهيكل المحدب المعتمدة على المخرجات هي Ω (n log h) في فضاء ثنائي الأبعاد.^[1] وهناك العديد من الخوارزميات تصل لهذا الحد الأدنى من التعقيد الزمني. وقد قدمها كيركباتريك وزايدل في عام 1986 (الذين أطلقوا عليها اسم خوارزمية الهيكل المحدب القصوى. ومن ثم تم طور شان خوارزمية أبسط بكثير في عام 1996، وسميت على اسمه خوارزمية شان.

خوارزميات الهيكل المحدب

خوارزميات الهيكل المحدب المدرجة أدناه مرتبة حسب تاريخ نشرها الأول. ونجد أن التعقيد الحسابي لكل خوارزمية قد مُثِل بعدد النقاط المدخلة n وعدد نقاط الهيكل المحدب h.

ملاحظة: قد تكون h مساوية ل n في أسوأ الحالات.

• خوارزمية جارفيس مارس أو (خوارزمية تغليف الهدايا) – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الأكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 وتبعهم آر جارفيس في عام 1973 بتعقيد زمني يقدر بO(nh). وفي أسوأ الحالات يكون Θ (n ²).
•  خوارزمية جراهام – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل رونالد جراهام في عام 1972. وتستغرق وقتاً يقدر بO (n) في حال كانت النقاط المدخلة مرتبة بناء على أحد الاحداثيات أو بناء على متجه ثابت.
• خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 وأ. بيكات 1978. وكخوارزمية الترتيب السريع فإن تعقيدها الزمني هو O(n log n) ومن الممكن ان تتراجع لتصل إلى O (n ²) في أسوء الحالات.
• خوارزمية فرق تسد – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ وفرانكو بريراتا بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.
•  خوارزمية اندرو (السلسلة الرتيبة) – O(n log n) نشر هذه الخوارزمية أندور في عام 1979. ويمكن اعتبار هذه الخوارزمية نوع من خوارزمية جراهام، التي ترتب النقاط من خلال إحداثياتها. وإذا تم ترتيب النقاط المدخلة فإن الخوارزمية تستغرق وقتاً يقدر ب O (n).
•  خوارزمية الهيكل المحدب المتزايد - O (n log n) تم صايغتها عام 1984 بواسطة مايكل كالي.
• خوارزمية كيركباتريك - سيدل - O (n log h) هي أول خوارزمية من الخوارزميات المعتمدة على المخرجات وتستخدم تقنية "marriage-before-conquest" في البرمجة الخطية محدودة الأبعاد. نشرت خوارزمية كيركباتريك وزايدل في عام 1986.
• خوارزمية تشان - O (n log h) نشرها تيموثي تشين في عام 1996. وهي خوارزمية مثلى من الخوارزميات المعتمدة على المخرجات وتعد أبسط من سابقاتها. وتدمج بين خوارزمية جارفيس واي خوارزمية تستغرق وقتا يقدر ب O(n log n)  -مثل خوارزمية جرهام - .

استدلال توسان وعقل

غالبًا ما يتم استخدام الاستدلال البسيط التالي كخطوة أولى في تنفيذ خوارزميات الهيكل المحدب لتحسين الأداء. وقد قام سليم عقل وتوسان باستحداث طريقة فعالة لايجاد الهيكل المحدب وتعتمد هذه الطريقة على استبعاد أكبر عدد ممكن من النقاط التي لا يمكن ان تشكل الهيكل المحدب من خلال إيجاد النقطتين اللتين تحتويان على أدنى وأعلى إحداثيات في محور x ، وأدنى وأعلى نقطتي إحداث في محور y. (كل من هذه العمليات تستغرق O(n)) وهذه النقاط الأربع تشكل محدباً رباعياً، وجميع النقاط التي تقع في هذا الرباعي (باستثناء الرؤوس الأربعة المختارة في البداية) ليست جزءًا من الهيكل المحدب أو يمكن أن نضيف إلى الشكل الرباعي النقاط التي تحتوي على أصغر وأكبر مجاميع من إحداثيات x وy وكذلك تلك التي تحتوي على أصغر وأكبر اختلافات في إحداثيات x و y ، وهطذا يصبح لدينا محدب ثماني غير منتظم، ثم نقوم بالتخلص من جميع النقاط التي بداخل الشكل الثماني بأمان.

إذا كانت النقاط عبارة عن متغيرات عشوائية -وهذا يكون فقط لفئة معينة وشائعة من دوال الكثافة الاحتمالية- فإن عملية التخلص من النقاط التي ذكرناها في الخطوة السابقة ستجعل الخوارزمية تستغرق زمناً خطياً، وحتى في اسوء الحالات فان الوقت المستغرق قد يصل إلى n ².^[2]

مشاكل خوارزمية الهيكل المحدب المتغير والفوري

ان في كل ما تم ذكره سابقا كانت النقاط المدخلة معروفة مسبقا، ولذلك فإننا يجب أن نأخذ بعين الاعتبار الخطوتين التاليتين عند بناء الهيكل المحدب:^[1]

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

قد يؤدي إدخال نقطة إلى زيادة عدد رؤوس الهيكل محدب بمقدار 1 على الأكثر، والعكس صحيح بالنسبة للحذف.

يمكن التعامل مع النقاط المدخلة للهيكل المحدب عبر الإنترنت خلال وقت يقدر ب O (log n) لكل نقطة، وهذا على أفضل تقدير. ويمكن التعامل مع النقاط المدخلة للهيكل المحدب المتغير خلال وقت يقدر ب O (log ² n) لكل عملية.^[1]

المضلع البسيط (مضلع بسيط)

يقسم الهيكل المحدب لمضلع بسيط إلى أجزاء من خلال جعل أحدها هو المضلع نفسه وأما باقي الهيكل فعبارة عن جيوب تحدها قطعة من حدود المضلع وحافة واحدة من الهيكل. على الرغم من نشر العديد من الخوارزميات لبناء الهيكل المحدب لمضلع بسيط، فإن نصفها تقريبًا غير صحيح.^[3] ويعد مكالوم وآفيس أول من قدم خوارزمية صحيحة.^[4] وقد استخدم جرهام وياو (Graham & Yao (1983)) ولي (Lee (1983)) بنية بيانات المكدس واحدة من أجل تبسيط الخوارزمية وتسير هذه الخوارزمية على المضلع في اتجاه عقارب الساعة، بدءً من النقطة الواقعة أقصى اليسار وخلال ذلك تقوم بتخزين النقاط الموجودة على المحدب (تلك التي لم يتم تحديدها بعد على أنها داخل الجيوب) في المكدس. في كل خطوة، تتبع الخوارزمية مسارًا على طول المضلع من قمة المكدس إلى النقطة التالية على ألا تكون ضمن أحد الجيوب المجاورة لأعلى المكدس. وطالما أن اخر نقطتين في أعلى المكدس لا يشكلان محدبا مع النقطة الجديدة نقوم بعملية إخراج النقطة العلوية من المكدس، ثم ادخال النقطة الجديدة. عندما تنتهي دورة قراءة الخوارزمية للنقاط في اتجاه عقارب الساعة نكون قد عدنا إلى نقطة البداية، وهنا ستكون نتيجة الخوارزمية عبارة عن تسلسل النقاط الموجودة في المكدس وهي ذاتها نقاط المكونة الهيكل.^[5][6]

مراجع

1. Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms"
2. Luc Devroye and Godfried Toussaint, "A note on linear expected time algorithms for finding convex hulls," Computing, Vol. 26, 1981, pp. 361-366.
3. Aloupis، Greg. "A History of Linear-time Convex Hull Algorithms for Simple Polygons". مؤرشف من الأصل في 2022-01-25. اطلع عليه بتاريخ 2020-10-11.
4. McCallum، Duncan؛ Avis، David (1979)، "A linear algorithm for finding the convex hull of a simple polygon"، Information Processing Letters، ج. 9، ص. 201–206، DOI:10.1016/0020-0190(79)90069-3، MR:0552534
5. Graham، Ronald L.؛ Yao، F. Frances (1983)، "Finding the convex hull of a simple polygon"، إلزيفير، ج. 4، ص. 324–331، DOI:10.1016/0196-6774(83)90013-5، MR:0729228
6. Lee، D. T. (1983)، "On finding the convex hull of a simple polygon"، International Journal of Computer and Information Sciences، ج. 12، ص. 87–98، DOI:10.1007/BF00993195، MR:0724699

قراءة متعمقة

• توماس إتش كورمن، تشارلز إي ليسرسون، رونالد إل ريفيست، وكليفورد شتاين. مقدمة في الخوارزميات ، الإصدار الثاني. مطبعة معهد ماساتشوستس للتكنولوجيا ومكجرو هيل، 2001.(ردمك 0-262-03293-7)رقم ISBN 0-262-03293-7 . القسم 33.3: العثور على بدن محدب، ص. 947-957 –
• فرانكو ب.بيراتا، إس جيه هونغ. هياكل محدبة من مجموعات محدودة من النقاط في بعدين وثلاثة أبعاد ، Commun. ACM ، المجلد. 20، لا. 2، ص. 87-93 – 1977.
• 978-3-540-65620-3 القسم 1.1: مثال: أجسام محدبة (يصف الخوارزميات الكلاسيكية للأجسام المحدبة ثنائية الأبعاد). الفصل 11: هياكل محدبة: ص. 235-250 – يصف خوارزمية عشوائية لهياكل محدبة ثلاثية الأبعاد بسبب كلاركسون وشور).

روابط خارجية

• Weisstein, Eric W. "Convex Hull". MathWorld.
• 2D, 3D, and dD Convex Hull in CGAL, the Computational Geometry Algorithms Library
• Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection
• Demo as Flash swf, Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
• Gift wrapping algorithm in C#