مستخدم:YasmeenAlslman/خوارزمية الهيكل المحدب

إن الخوارزميات التي تبني هياكلاً محدبة (convex hull) لها العديد من الاستخدامات الواسعة في الرياضيات وعلوم الحاسوب.

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

خوارزمية جارفيس مارس او (خوارزمية تغليف الهدايا) – O (nh) هي واحدة من أبسط الخوارزميات المستوية (ثنائية الأبعاد) بالرغم من أنها ليست الاكثر كفاءة من ناحية الوقت الحسابي في أسوأ الحالات. إن أول من صاغ هذه الخوارزمية هم تشاند وكابور في عام 1970 و تبعهم آر جارفيس في عام 1973 بتعقيد زمني يقدر بO(nh). و في أسوأ الحالات يكون Θ (n ²).
خوارزمية جراهام – O (n log n) تعتبر هذه خوارزمية أكثر تعقيدًا من الخوارزمية السابقة إلى حد ما ، ولكنها أكثر فاعلية. وقد تم صياغة هذه الخوارزمية من قبل رونالد جراهام في عام 1972. و تستغرق وقتاً يقدر بO ( n ) في حال كانت النقاط المدخلة مرتبة بناء على احد الاحداثيات او بناء على متجه ثابت.
خوارزمية الهيكل السريعة (Quick hull) تم صياغة هذه الخوارزمية من قبل إيدي 1977 و أ. بيكات 1978. و كخوارزمية الترتيب السريع (Quick sort) فان تعقيدها الزمني هو O(n log n) و من الممكن ان تتراجع لتصل الى O ( n ² ) في أسوء الحالات.
خوارزمية فرق تسد – O(n log n) في عام 1977 قام بصياغة هذه الخوارزمية هونغ و فرانكو بريراتا (Franco Preparata and Hong) بوقت حسابي يقدر ب O(n log n) وهذه الخوارزمية مناسبة إذا كانت النقاط المراد ادخالها في الخوارزمية ثلاثية الأبعاد.
خوارزمية اندرو (السلسلة الرتيبة) – O(n log n) تم نشر هذه الخوارزمية عام 1979 بواسطة اندرو AM Andrew. و يمكن اعتبار هذه الخوارزمية كنوع من خوارزمية جراهام ، التي ترتب النقاط من خلال إحداثياتها. و إذا تم ترتيب النقاط المدخلة فإن الخوارزمية تستغرق وقتاً يقدر ب O (n).
خوارزمية الهيكل المحدب المتزايد - O (n log n) تم صايغتها عام 1984 بواسطة مايكل كاليMichael Kallay.
خوارزمية كيركباتريك - سيدل - O ( n log h ) هي أول خوارزمية من الخوارزميات المعتمدة على المخرجات و تستخدم تقنية "marriage-before-conquest" في البرمجة الخطية محدودة الأبعاد. وقد تم نشرها بواسطة Kirkpatrick and Seidel عام 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]

المضلع البسيط (Simple Polygon)[عدل]

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

مراجع[عدل]

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

[ps-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". اطلع عليه بتاريخ 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 ع. 5: 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"، Journal of Algorithms، ج. 4 ع. 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 ع. 2: 87–98، DOI:10.1007/BF00993195، MR:0724699

[1]

[2]

[3]

[4]

[5]

[6]