خوارزمية تشان

تتطلب عملية تمرير واحدة للخوارزمية معلمة${\displaystyle m}$والتي تقع بين 0 و${\displaystyle n}$(عدد نقاط مجموعتنا)${\displaystyle P}$). من الناحية المثالية،${\displaystyle m=h}$لكن${\displaystyle h}$عدد الرؤوس في الغلاف المحدب الناتج غير معروف في البداية. يتم إجراء عدة تمريرات بقيم متزايدة لـ${\displaystyle m}$يتم إنجازها، ثم تنتهي عندما${\displaystyle m\geq h}$انظر أدناه حول اختيار المعلمة${\displaystyle m}$.

تبدأ الخوارزمية بتقسيم مجموعة النقاط بشكل عشوائي${\displaystyle P}$داخل${\displaystyle K=\lceil n/m\rceil }$المجموعات الفرعية${\displaystyle (Q_{k})_{k=1,2,...K}}$مع أقصى حد${\displaystyle m}$لكل نقطة؛ لاحظ أن${\displaystyle K=O(n/m)}$.

لكل مجموعة فرعية${\displaystyle Q_{k}}$، حيث يقوم بحساب الغلاف المحدب،${\displaystyle C_{k}}$باستخدام${\displaystyle O(p\log p)}$خوارزمية (على سبيل المثال، مسح غراهام )، حيث${\displaystyle p}$يمثل عدد النقاط في المجموعة الفرعية. حيث يوجد${\displaystyle K}$مجموعات فرعية من${\displaystyle O(m)}$كل نقطة، هذه المرحلة تستغرق${\displaystyle K\cdot O(m\log m)=O(n\log m)}$وقت.

خلال المرحلة الثانية، يتم تنفيذ مسيرة جارفيس ، باستخدام الأغلفة المحدبة (الصغيرة) المحسوبة مسبقًا.${\displaystyle (C_{k})_{k=1,2,...K}}$في كل خطوة من خطوات خوارزمية مسيرة جارفيس هذه، لدينا نقطة${\displaystyle p_{i}}$في الغلاف المحدب (في البداية،${\displaystyle p_{i}}$ربما تكون هذه هي النقطة في${\displaystyle P}$بأقل إحداثي y، والذي يضمن وجوده في الغلاف المحدب لـ${\displaystyle P}$)، ويحتاجون إلى إيجاد نقطة${\displaystyle p_{i+1}=f(p_{i},P)}$بحيث تكون جميع النقاط الأخرى${\displaystyle P}$تقع على يمين الخط${\displaystyle p_{i}p_{i+1}}$، حيث الترميز${\displaystyle p_{i+1}=f(p_{i},P)}$يعني ذلك ببساطة أن النقطة التالية هي${\displaystyle p_{i+1}}$يتم تحديدها كدالة لـ${\displaystyle p_{i}}$و${\displaystyle P}$الغلاف المحدب للمجموعة${\displaystyle Q_{k}}$،${\displaystyle C_{k}}$، وهو معروف ويحتوي على الأكثر${\displaystyle m}$النقاط (المدرجة بترتيب مع عقارب الساعة أو عكس عقارب الساعة)، مما يسمح بحساب${\displaystyle f(p_{i},Q_{k})}$في${\displaystyle O(\log m)}$الوقت باستخدام البحث الثنائي . ومن ثم، حساب${\displaystyle f(p_{i},Q_{k})}$لكل${\displaystyle K}$يمكن إجراء المجموعات الفرعية في${\displaystyle O(K\log m)}$الوقت. عندها، يمكننا تحديد${\displaystyle f(p_{i},P)}$باستخدام نفس الأسلوب المستخدم عادةً في مسيرة جارفيس، ولكن مع مراعاة النقاط فقط${\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}$(أي النقاط الموجودة في الأغلفة المحدبة المصغرة) بدلاً من المجموعة بأكملها${\displaystyle P}$بالنسبة لتلك النقاط، فإن إحدى نسخ مسيرة جارفيس هي${\displaystyle O(K)}$وهو أمر ضئيل مقارنةً بالحسابات الخاصة بجميع المجموعات الفرعية. تكتمل مسيرة جارفيس عند تكرار العملية.${\displaystyle O(h)}$مرات (لأن، بحسب طريقة عمل مسيرة جارفيس، بعد أكثر من${\displaystyle h}$تكرارات حلقتها الخارجية، حيث${\displaystyle h}$يمثل عدد النقاط في الغلاف المحدب لـ${\displaystyle P}$، لا بد أننا وجدنا الغلاف المحدب)، ومن ثم تبدأ المرحلة الثانية${\displaystyle O(Kh\log m)}$الوقت، المكافئ لـ${\displaystyle O(n\log h)}$الوقت إذا${\displaystyle m}$قريب من${\displaystyle h}$(انظر أدناه وصفًا لاستراتيجية للاختيار)${\displaystyle m}$بحيث يكون هذا هو الحال).

من خلال تنفيذ المرحلتين الموصوفتين أعلاه، يتم الحصول على الغلاف المحدب لـ${\displaystyle n}$يتم حساب النقاط في${\displaystyle O(n\log h)}$وقت.

إذا تم اختيار قيمة عشوائية لـ${\displaystyle m}$قد يحدث أن${\displaystyle m<h}$في هذه الحالة، بعد${\displaystyle m}$في المرحلة الثانية، نوقف مسيرة جارفيس لأن إكمالها حتى النهاية سيستغرق وقتاً طويلاً. في تلك اللحظة،${\displaystyle O(n\log m)}$سيكون الوقت قد انقضى، ولن يتم حساب الغلاف المحدب.

الفكرة هي إجراء عدة دورات للخوارزمية بقيم متزايدة لـ${\displaystyle m}$تنتهي كل محاولة (بنجاح أو بفشل) في${\displaystyle O(n\log m)}$الوقت. إذا${\displaystyle m}$إذا زادت القيمة ببطء شديد بين الدورات، فقد يكون عدد التكرارات كبيرًا؛ من ناحية أخرى، إذا ارتفعت بسرعة كبيرة، فإن الدورة الأولى${\displaystyle m}$قد تكون القيم التي تنتهي عندها الخوارزمية بنجاح أكبر بكثير من${\displaystyle h}$وتنتج تعقيدًا${\displaystyle O(n\log m)>O(n\log h)}$.

ولتعميم هذا البناء على الحالة ثلاثية الأبعاد،${\displaystyle O(n\log n)}$ينبغي استخدام خوارزمية بريباراتا وهونغ لحساب الغلاف المحدب ثلاثي الأبعاد بدلاً من مسح غراهام، كما يجب استخدام نسخة ثلاثية الأبعاد من مسيرة جارفيس. ويبقى التعقيد الزمني كما هو.${\displaystyle O(n\log h)}$[ ^{1 ]​}

في الشفرة الزائفة التالية ، تُعتبر النصوص بين قوسين والمكتوبة بخط مائل تعليقات. لفهم الشفرة الزائفة التالية فهمًا كاملًا، يُنصح بأن يكون القارئ على دراية مسبقة بخوارزميات مسح غراهام وجارفيس لحساب الغلاف المحدب.${\displaystyle C}$، لمجموعة من النقاط، ${\displaystyle P}$.

الإدخال: ضبط${\displaystyle P}$مع${\displaystyle n}$نقاط.

الناتج: مجموعة${\displaystyle C}$مع${\displaystyle h}$النقاط، الغلاف المحدب لـ${\displaystyle P}$.

(اختر نقطة من${\displaystyle P}$وهو أمر مضمون أن يكون في${\displaystyle C}$(على سبيل المثال، النقطة ذات الإحداثي y الأدنى.)

(تستغرق هذه العملية${\displaystyle {\mathcal {O}}(n)}$الوقت: على سبيل المثال، يمكننا ببساطة التكرار من خلال${\displaystyle P}$.)

${\displaystyle p_{1}:=PICK\_START(P)}$

(${\displaystyle p_{0}}$يُستخدم في جزء مسيرة جارفيس من خوارزمية تشان هذه،

وبالتالي لحساب النقطة الثانية،${\displaystyle p_{2}}$، في الغلاف المحدب لـ${\displaystyle P}$.)

(ملحوظة:${\displaystyle p_{0}}$ليست نقطة من${\displaystyle P}$.)

(للمزيد من المعلومات، انظر التعليقات القريبة من الجزء المقابل من خوارزمية تشان.)

${\displaystyle p_{0}:=(-\infty ,0)}$

(ملحوظة:${\displaystyle h}$، عدد النقاط في الغلاف المحدب النهائي لـ${\displaystyle P}$( غير معروف.)

(هذه هي التكرارات اللازمة لاكتشاف قيمة${\displaystyle m}$وهو تقدير لـ${\displaystyle h}$.)

(${\displaystyle h\leq m}$هذا مطلوب لخوارزمية تشان لإيجاد الغلاف المحدب لـ${\displaystyle P}$.)

(وبشكل أكثر تحديدًا، نريد${\displaystyle h\leq m\leq h^{2}}$حتى لا يتم إجراء الكثير من التكرارات غير الضرورية

وبالتالي فإن التعقيد الزمني لخوارزمية تشان هذه هو${\displaystyle {\mathcal {O}}(n\log h)}$.)

(كما هو موضح أعلاه في هذه المقالة، يتم استخدام استراتيجية حيث يكون الحد الأقصى${\displaystyle \log \log n}$يلزم إجراء تكرارات للعثور على${\displaystyle m}$.)

(ملاحظة: النهائي)${\displaystyle m}$قد لا يكون مساوياً لـ${\displaystyle h}$لكنها لا تكون أصغر من ذلك أبداً${\displaystyle h}$وأكبر من${\displaystyle h^{2}}$.)

(ومع ذلك، تتوقف خوارزمية تشان هذه بمجرد${\displaystyle h}$يتم تنفيذ تكرارات الحلقة الخارجية،

أي حتى لو${\displaystyle m\neq h}$لا يؤدي الغرض المطلوب${\displaystyle m}$تكرارات الحلقة الخارجية.)

(للمزيد من المعلومات، انظر إلى جزء مسيرة جارفيس من هذه الخوارزمية أدناه، حيث${\displaystyle C}$يتم إرجاعها إذا${\displaystyle p_{i+1}==p_{1}}$.)

ل${\displaystyle 1\leq t\leq \log \log n}$يفعل

(ضبط المعلمة)${\displaystyle m}$بالنسبة للتكرار الحالي. يتم استخدام "مخطط التربيع" كما هو موضح أعلاه في هذه المقالة.

توجد مخططات أخرى: على سبيل المثال، "مخطط المضاعفة"، حيث${\displaystyle m=2^{t}}$، ل${\displaystyle t=1,\dots ,\left\lceil \log h\right\rceil }$.

أما إذا تم استخدام "مخطط المضاعفة"، فإن التعقيد الزمني الناتج لخوارزمية تشان هذه هو${\displaystyle {\mathcal {O}}(n\log ^{2}h)}$.)

${\displaystyle m:=2^{2^{t}}}$

(قم بتهيئة قائمة (أو مصفوفة) فارغة لتخزين نقاط الغلاف المحدب لـ${\displaystyle P}$(كما يتم العثور عليها.)

${\displaystyle C:=()}$

${\displaystyle ADD(C,p_{1})}$

(مجموعة نقاط مقسمة بشكل عشوائي)${\displaystyle P}$داخل${\displaystyle K=\left\lceil {\frac {n}{m}}\right\rceil }$مجموعات فرعية من تقريبًا${\displaystyle m}$كل عنصر من العناصر.)

${\displaystyle Q_{1},Q_{2},\dots ,Q_{K}:=SPLIT(P,m)}$

(احسب الغلاف المحدب لجميع${\displaystyle K}$مجموعات فرعية من النقاط،${\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}$.)

(فإنه يأخذ${\displaystyle {\mathcal {O}}(Km\log m)={\mathcal {O}}(n\log m)}$وقت.)

لو${\displaystyle m\leq h^{2}}$إذن، يكون التعقيد الزمني هو${\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}$.)

ل${\displaystyle 1\leq k\leq K}$يفعل

(احسب الغلاف المحدب للمجموعة الجزئية)${\displaystyle k}$،${\displaystyle Q_{k}}$باستخدام مسح غراهام، الذي يأخذ${\displaystyle {\mathcal {O}}(m\log m)}$وقت.)

(${\displaystyle C_{k}}$هو الغلاف المحدب لمجموعة النقاط الفرعية${\displaystyle Q_{k}}$.)

${\displaystyle C_{k}:=GRAHAM\_SCAN(Q_{k})}$

(عند هذه النقطة، الأغلفة المحدبة${\displaystyle C_{1},C_{2},\dots ,C_{K}}$من مجموعات النقاط الفرعية على التوالي${\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}$(تم حسابها.)

(الآن، استخدم نسخة معدلة من خوارزمية مسيرة جارفيس لحساب الغلاف المحدب لـ${\displaystyle P}$.)

(يؤدي جارفيس مارش عرضه في${\displaystyle {\mathcal {O}}(nh)}$الوقت، أين${\displaystyle n}$يمثل عدد نقاط الإدخال و${\displaystyle h}$(عدد النقاط في الغلاف المحدب.)

(نظرًا لأن خوارزمية جارفيس مارش حساسة للمخرجات ، فإن وقت تشغيلها يعتمد على حجم الغلاف المحدب،${\displaystyle h}$.)

(عمليًا، هذا يعني أن مسيرة جارفيس تؤدي${\displaystyle h}$تكرارات الحلقة الخارجية.

في كل تكرار من هذه التكرارات، يكون أداؤه على الأكثر${\displaystyle n}$تكرارات الحلقة الداخلية الخاصة بها.)

(نريد)${\displaystyle h\leq m\leq h^{2}}$لذلك لا نريد أن نؤدي أكثر من${\displaystyle m}$(تكرارات في الحلقة الخارجية التالية.)

(إذا كان التيار${\displaystyle m}$أصغر من${\displaystyle h}$، أي${\displaystyle m<h}$، الغلاف المحدب لـ${\displaystyle P}$(لا يمكن العثور عليه.)

(في هذه النسخة المعدلة من مسيرة جارفيس، نقوم بتنفيذ عملية داخل الحلقة الداخلية التي تأخذ${\displaystyle {\mathcal {O}}(\log m)}$وقت.

وبالتالي، فإن التعقيد الزمني الإجمالي لهذه النسخة المعدلة هو

${\displaystyle {\mathcal {O}}(mK\log m)={\mathcal {O}}(m\left\lceil {\frac {n}{m}}\right\rceil \log m)={\mathcal {O}}(n\log m)={\mathcal {O}}(n\log 2^{2^{t}})={\mathcal {O}}(n2^{t}).}$

لو${\displaystyle m\leq h^{2}}$إذن، يكون التعقيد الزمني هو${\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}$.)

ل${\displaystyle 1\leq i\leq m}$يفعل

(ملاحظة: هنا، نقطة في الغلاف المحدب لـ${\displaystyle P}$هذا أمر معروف بالفعل، أي${\displaystyle p_{1}}$.)

(في حلقة التكرار الداخلية هذه ،${\displaystyle K}$النقاط التالية المحتملة التي يجب أن تكون على الغلاف المحدب لـ${\displaystyle P}$،${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$(يتم حسابها.)

(كل من هؤلاء${\displaystyle K}$النقاط المحتملة التالية تأتي من منظور مختلف${\displaystyle C_{k}}$:

إنه،${\displaystyle q_{i,k}}$هي نقطة محتملة تالية على الغلاف المحدب لـ${\displaystyle P}$وهو جزء من الغلاف المحدب لـ${\displaystyle C_{k}}$.)

(ملحوظة:${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$يعتمد على${\displaystyle i}$أي، لكل تكرار${\displaystyle i}$، هناك${\displaystyle K}$النقاط التالية المحتملة التي يجب أن تكون على الغلاف المحدب لـ${\displaystyle P}$.)

(ملاحظة: في كل تكرار)${\displaystyle i}$، وهي واحدة فقط من النقاط بين${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$تُضاف إلى الغلاف المحدب لـ${\displaystyle P}$.)

ل${\displaystyle 1\leq k\leq K}$يفعل

(${\displaystyle JARVIS\_BINARY\_SEARCH}$يجد النقطة${\displaystyle d\in C_{k}}$بحيث تكون الزاوية${\displaystyle \measuredangle p_{i-1}p_{i}d}$يتم تحقيق أقصى قدر من الكفاءة ،

أين${\displaystyle \measuredangle p_{i-1}p_{i}d}$الزاوية بين المتجهين${\displaystyle {\overrightarrow {p_{i}p_{i-1}}}}$و${\displaystyle {\overrightarrow {p_{i}d}}}$. هذه${\displaystyle d}$يتم تخزينها في${\displaystyle q_{i,k}}$.)

(لا يلزم حساب الزوايا مباشرة: يمكن استخدام اختبار التوجيه .)

(${\displaystyle JARVIS\_BINARY\_SEARCH}$يمكن تنفيذه في${\displaystyle {\mathcal {O}}(\log m)}$وقت .)

(ملاحظة: في التكرار${\displaystyle i=1}$،${\displaystyle p_{i-1}=p_{0}=(-\infty ,0)}$و${\displaystyle p_{1}}$معروفة وهي نقطة في الغلاف المحدب لـ${\displaystyle P}$:

في هذه الحالة، تكمن الفكرة في${\displaystyle P}$(مع أدنى قيمة للإحداثي y.)

${\displaystyle q_{i,k}:=JARVIS\_BINARY\_SEARCH(p_{i-1},p_{i},C_{k})}$

(اختر النقطة)${\displaystyle z\in \{q_{i,1},q_{i,2},\dots ,q_{i,K}\}}$مما يزيد الزاوية إلى أقصى حد${\displaystyle \measuredangle p_{i-1}p_{i}z}$لتكون النقطة التالية على الغلاف المحدب لـ${\displaystyle P}$.)

${\displaystyle p_{i+1}:=JARVIS\_NEXT\_CH\_POINT(p_{i-1},p_{i},(q_{i,1},q_{i,2},\dots ,q_{i,K}))}$

(تنتهي مسيرة جارفيس عند النقطة المحددة التالية على الهيكل المحدب،${\displaystyle p_{i+1}}$، هي النقطة الابتدائية،${\displaystyle p_{1}}$.)

لو${\displaystyle p_{i+1}==p_{1}}$

(أعد الغلاف المحدب لـ${\displaystyle P}$والذي يحتوي${\displaystyle i=h}$نقاط.)

(ملاحظة: بالطبع، لا داعي للعودة)${\displaystyle p_{i+1}}$وهو ما يساوي${\displaystyle p_{1}}$.)

يعود${\displaystyle C:=(p_{1},p_{2},\dots ,p_{i})}$

آخر

${\displaystyle ADD(C,p_{i+1})}$

(إفستان)${\displaystyle m}$تكرارات نقطة${\displaystyle p_{i+1}}$لم يتم العثور عليه، لذلك${\displaystyle p_{i+1}==p_{1}}$، ثم${\displaystyle m<h}$.)

(نحتاج إلى البدء من جديد بقيمة أعلى لـ${\displaystyle m}$.)