الگوریتم‌های پوش محدب

الگوریتمی که پوش محدب اشیای مختلف را به دست می‌دهد کاربردهای وسیعی در ریاضیات و علوم کامپیوتر دارد. در هندسه محاسباتی، الگوریتم‌های متعددی با پیچیدگی‌های محاسباتی گوناگون برای محاسبه پوش محدب مجموعه‌ای محدود از نقاط مطرح شده‌است. محاسبه پوش محدب به معنی ارائه نمایشی نامبهم و کارا از شکل مطلوب می‌باشد. پیچیدگیهای الگوریتم‌های مربوطه معمولاً بر حسب n، تعداد نقاط ورودی، و h، تعداد نقاط درون پوش محدب، سنجیده می‌شوند.

حالت دو بعدی

اگر همهٔ نقاط روی یک صفحه نباشند آنگاه پوش محدب حاصلچندظلعی محدبی می‌شود که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. معمولترین نمایش پوشه محدب به صورت لیستی از رأس‌های آن می‌باشد که ترتیب آن بر اساس پیمایشی ساعتگرد یا پادساعتگرد بر روی مرز پوش محدب می‌باشد. در بعضی از کاربردها نمایش این چندظلعی  محدب به صورت اشتراک تعدادی نیم صفحه مناسب تر می‌باشد.

کران پایین پیچیدگی محاسباتی

کران پایین محاسباتی برای پیدا کردن پوش محدب و نمایش آن به صورت چند ضلعی  محدب، مشابه  این کران برای مرتب‌سازی می‌باشد و به سادگی می‌توان این مطلب را با کاهش نشان داد. برای نقاط  که می‌خواهیم مرتب کنیم، نقاط  را بر روی صفحه در نظر بگیرید. حال چون این نقاط بر روی سهمی که منحنی محدب است قرار دارند به راحتی می‌توان دید که پیمایش بر روی مرز پوش محدب آن‌ها ترتیب مرتب شدهٔ این اعداد را می‌دهد. به وضوح  زمان خطی برای تبدیل اعداد به نقاط و سپس به دست آوردن ترتیب مرتب شده، نیاز می‌باشد. از این رو به دست آوردن پوش محدب  n نقطه نمی‌تواند سریعتر از مرتبسازی عمل کند.
کران پایین محاسباتی استاندارد به کمک مدل درخت تصمیم می‌باشد  که البته در این مدل تنها مقایسه انجام می‌شود و نه عملیات محاسباتی. به هر حال پوش محدب در این مدل نمی‌تواند محاسبه شود. مرتب‌سازی در مدلدرخت تصمیم جبری نیز از  می‌باشد که این مدل برای پوش محدب مناسبتر می‌باشد که در این مدل نیز به دست آوردن پوش محدب‌ها زمانی از   می‌خواهد. هر چند در مدل‌هایی که اجازه می‌دهند که اعداد سریعتر از  مرتب شودند، برای نمونه الگوریتم هایinteger sorting، پوش محدب نیز می‌تواند سریعتر محاسبه شود: الگوریتم پیمایش گراهام شامل یک مرحله سادهٔ مرتب‌سازی است که به دنبال مقداری کار اضافه که در زمان خطی انجام می‌شوند امده‌اند.

الگوریتم حساس به خروجی بهینه

همان که در بالا ذکر شد پیچیدگی پیدا کردن پوش محدب به صورت تابعی از تعداد نقاط ورودی  می‌باشد. هر چند که پیچیدگی بعضی از الگوریتم‌های پوش محدب بر حسب سایز ورودی n و سایز خروجی h (تعداد نقاط روی پوش محدب) عنوان می‌شود. این گونه الگورتم‌ها حساس به خروجی نامیده می‌شوند. این الگوریتم‌ها ممکن است به‌طور مجانبی کارا تر از  باشند در حالتی که 
کران پایین در بدترین حالت زمانی الگوریتم‌های مربوط به پوش محدب حساس به خروجی در حالت دوبعدی می‌باشد.الگوریتم‌های متعددی وجود دارند که این پیچیدگی بهینه را به دست می‌دهند. اولین آن‌ها در سال ۱۹۸۶ توسط Kirkpatrick و Seidel معرفی شد (که آن را الگوریتم نهایی پوش محدب نامیدند.)الگوریتم ساده‌تر توسط Chan در ۱۹۹۶ داده شد که الگوریتم چان نامیده شد.

الگوریتم ابتکاری (heuristic) Alk-Toussaint

ابتکار ساده‌ای که در ادامهٔ کار می‌آید اغلب اولین مرحله در پیاده‌سازی الگوریتم پوش محدب برای بهبود کارایی آن می‌باشد. پایهٔ آن بر اساس اگوریتمی کارا که در سال ۱۹۷۸ توسطSelim Akl و G.T.Toussaint ارائه شد. ایدهٔ کار به این صورت است که به‌طور سریع نقاطی که به هیچ وجه نمی‌توانند در پوش محدب باشند را حذف کنیم. این روش بر مبنای آن است که در ادامه می‌آید. دو نقطه‌ای را که دارای کمترین و بیشترین مختصات x می‌باشند و به همین ترتیب دو نقطه‌ای که دارای کمترین و بیشترین مختصات y اند را پیدا می‌کنیم.(این کار در  انجام می‌شود.)این چهار نقطه تشکیل یک چهار ظلعی محدب را می‌دهند و تمام نقاطی که در این چهار ظلعی قرار می‌گیرند (غیر از چهار نقطهٔ ابتدایی) نمی‌توانند درون پوش محدب باشند. پیدا کردن تمامی نقاطی که درون این چهار ظلعی قرار می‌گیرند نیز   هزینه می‌برد، پس در کل تا اینجا از   هزینه کرده‌ایم. به‌طور دلخواه نقاط با کمترین  و بیشترین مجموع x,y و نقاط با کمترین و بیشترین تفاضل x,y را نیز می‌توانند به چهار ظلعی قبلی اضافه شوند تا این نقاط بر روی هم یک ۸ ظلعی محدب را به وجود آورند که نقاط درون آن به راحتی می‌توانند حذف شوند. اگر نقاط ورودی به صورت رندم انتخاب شوند آنگاه برای کلاسی گسترده از تابع‌های چگالی احتمال، این دور انداختن بعضی از نقاط در پیش پردازش باعث می‌شود که الگوریتمی که اجرا می‌شود دارای  پیچیگی زمانی باشد که امید ریاضی آن خطی باشد، حتی اگر در بدترین حالت از   باشد.

به دست آوردن پوش محدب چندضلعی ساده

McCallum و Avis اولین نفراتی بودند که پوش محدب برای یک چندظلعی ساده با رأس‌های   را در) ساختند. ایدهٔ اصلی بسیار ساده است. چپترین نقطه روی پوش محدب می‌باشد و ما آن را با  مشخص می‌کنیم. دومین نقطه را نیز به عنوان کاندیدی برای راس پوش فرض می‌کنیم. در هر مرحله به سه راس متوالی نگاه می‌کنیم که دو تای اول به عنوان رأس‌های موقت پوش اختصاص داده شده‌اند و راس سوم هنوز پردازش نشده‌است که ما آن‌ها را به صورت مشخص می‌کنیم. اگر زاویهٔ بین آن‌ها محدب بود  انگاه   و این سه تایی با یک انتقال یک راسی سه تایی بعدی را مشخص می‌کند. اما اگر زاویهٔ ایجاد شده مقعر باشد آنگاه نقطه میانی()  پاک شده و این تست برای سه تایی  تا تکرار می‌کنیم تا این که یا به زاویهٔ محدب رسیده یا این که به   و بعد از نقطهٔ بعدی به سه تایی برای تست شدن اضافه می‌شود و این روند تکرار می‌شود. هر چند که در تعدادی از مقالاتی که در گذشته انتشار یافته‌اند از امکان خود متقاطع شدن چند ضلعی در حین حذف رءوس صحبت شده که  دلیلی بر نامعتبر بودن روند این الگوریتم می‌باشد. خوشبختانه، این مورد نیز به صورت کارا مدیریت می‌شود. بعداً Tor و Middleditch و به صورت مستقل Melkman  رویکردی ساده‌تر با پیچیدگی زمانی یکسان ارائه کردند.

بعدهای بالاتر

شماری از الگوریتم‌ها برای سه بعد وجود دارد، همچنین برای بعدهای دلخواه: نگاه کنید به:https://web.archive.org/web/20070609032115/http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
برای مجموعه‌ای محدود از نقاط در سه بعد پوش محدب به صورت یک چند وجهی محدب می‌باشد یا به‌طور کلی یک چندوجهی محدب برای هر تعداد بعد، که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. نمایش آن به سادگی نمایش در بعد نمی‌باشد. در بعدهای بالاتر حتی اگر رأس‌های این چند وجهی معلوم باشند. ساختن وجههای آن کاری بدیهی نیست. همچنین دوگان این مسئله نیز این چنین است یعنی پیدا کردن رأس‌ها از روی وجه‌ها. سایز خروجی می‌تواند به صورت نمایی از سایز ورودی بیشتر باشد، حتی در شرایطی که سایز خروجی و ورودی قابل مقایسه باشد الگوریتم‌های ارائه شده برای بعدهای بالاتر حساس به خروجی نیستند.