الگوریتم‌های پوش محدب
الگوریتمی که پوش محدب اشیای مختلف را به دست می‌دهد کاربردهای وسیعی در ریاضیات و علوم کامپیوتر دارد. در هندسه محاسباتی، الگوریتم‌های متعددی با پیچیدگی‌های محاسباتی گوناگون برای محاسبه پوش محدب مجموعه‌ای محدود از نقاط مطرح شده‌است. محاسبه پوش محدب به معنی ارائه نمایشی نامبهم و کارا از شکل مطلوب می‌باشد. پیچیدگیهای الگوریتم‌های مربوطه معمولاً بر حسب n، تعداد نقاط ورودی، و h، تعداد نقاط درون پوش محدب، سنجیده می‌شوند.
اگر همهٔ نقاط روی یک صفحه نباشند آنگاه پوش محدب حاصلچندظلعی محدبی می‌شود که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. معمولترین نمایش پوشه محدب به صورت لیستی از رأس‌های آن می‌باشد که ترتیب آن بر اساس پیمایشی ساعتگرد یا پادساعتگرد بر روی مرز پوش محدب می‌باشد. در بعضی از کاربردها نمایش این چندظلعی محدب به صورت اشتراک تعدادی نیم صفحه مناسب تر می‌باشد.
کران پایین محاسباتی برای پیدا کردن پوش محدب و نمایش آن به صورت چند ضلعی محدب، مشابه این کران برای مرتب‌سازی می‌باشد و به سادگی می‌توان این مطلب را با کاهش نشان داد. برای نقاط formula_1 که می‌خواهیم مرتب کنیم، نقاط formula_2 را بر روی صفحه در نظر بگیرید. حال چون این نقاط بر روی سهمی که منحنی محدب است قرار دارند به راحتی می‌توان دید که پیمایش بر روی مرز پوش محدب آن‌ها ترتیب مرتب شدهٔ این اعداد را می‌دهد. به وضوح زمان خطی برای تبدیل اعداد به نقاط و سپس به دست آوردن ترتیب مرتب شده، نیاز می‌باشد. از این رو به دست آوردن پوش محدب n نقطه نمی‌تواند سریعتر از مرتبسازی عمل کند.
کران پایین محاسباتی استاندارد به کمک مدل درخت تصمیمformula_3 می‌باشد که البته در این مدل تنها مقایسه انجام می‌شود و نه عملیات محاسباتی. به هر حال پوش محدب در این مدل نمی‌تواند محاسبه شود. مرتب‌سازی در مدلدرخت تصمیم جبری نیز از formula_3 می‌باشد که این مدل برای پوش محدب مناسبتر می‌باشد که در این مدل نیز به دست آوردن پوش محدب‌ها زمانی از formula_3 می‌خواهد. هر چند در مدل‌هایی که اجازه می‌دهند که اعداد سریعتر از formula_6 مرتب شودند، برای نمونه الگوریتم هایinteger sorting، پوش محدب نیز می‌تواند سریعتر محاسبه شود: الگوریتم پیمایش گراهام شامل یک مرحله سادهٔ مرتب‌سازی است که به دنبال مقداری کار اضافه که در زمان خطی انجام می‌شوند امده‌اند.
همان که در بالا ذکر شد پیچیدگی پیدا کردن پوش محدب به صورت تابعی از تعداد نقاط ورودی formula_3 می‌باشد. هر چند که پیچیدگی بعضی از الگوریتم‌های پوش محدب بر حسب سایز ورودی n و سایز خروجی h (تعداد نقاط روی پوش محدب) عنوان می‌شود. این گونه الگورتم‌ها حساس به خروجی نامیده می‌شوند. این الگوریتم‌ها ممکن است به‌طور مجانبی کارا تر از formula_3 باشند در حالتی که formula_9
کران پایین در بدترین حالت زمانی الگوریتم‌های مربوط به پوش محدب حساس به خروجی در حالت دوبعدی formula_3می‌باشد.الگوریتم‌های متعددی وجود دارند که این پیچیدگی بهینه را به دست می‌دهند. اولین آن‌ها در سال ۱۹۸۶ توسط Kirkpatrick و Seidel معرفی شد (که آن را الگوریتم نهایی پوش محدب نامیدند.)الگوریتم ساده‌تر توسط Chan در ۱۹۹۶ داده شد که الگوریتم چان نامیده شد.
الگوریتم‌های شناخته شدهٔ مربوط به پوش محدب در زیر لیست شده‌اند که آن‌ها را بر اساس اولین تاریخ انتشار مرتب کرده‌ایم. پیچیدگی زمانی این الگوریتم‌ها بر اساس تعداد نقاط ورودی n و تعداد نقاط روی پوش محدب h بیان شده‌اند. توجه شود که در بدترین حالت h ممکن است به بزرگی n باشد. یکی از ساده‌ترین (اگر چه مؤثرترین در بدترین حالت نمی‌باشد) الگوریتم‌های صفحه‌ای می‌باشد که به‌طور مستقل توسط Chand و Kapur در ۱۹۹۰ و R.A.Jarvis در ۱۹۷۳ کشف شد. این الگوریتم دارای پیچیدگی زمانی formula_11 می‌باشد و در بدترین حالت این پیچیدگی از مرتبه formula_12 است. یک الگوریتم با کمی پیچیدگی بیشتر ولی کاراتر که در سال ۱۹۷۲ توسط رونالد گراهام انتشار یافت. اگر نقاط قبلاً بر اساس یکی از مؤلفه‌های مختصاتشان یا بر اساس زاویه با برداری ثابت مرتب شده باشند آنگاه این الگوریتم از formula_13 می‌باشد. به‌طور مستقل توسط W.Eddy در ۱۹۷۷ و A.Bykat در ۱۹۷۸ کشف شد. درست مانند مرتب‌سازی سریع به‌طور میانگین ازformula_14 است ولی ممکن است در بدترین حالت به formula_15 برسد. الگوریتم دیگری از formula_6 که در سال ۱۹۷۷ توسطPreparata و Hong انتشار یافت. این اگوریتم برای حالت سه بعدی نیز قابل اجرا می‌باشد. در سال ۱۹۷۹ توسط A.M.Andrew انتشار یافت. به این الگوریتم می‌توان به دید تغییر شکل یافتهٔ Graham scan نگاه کرد که در آن نقاط بر اساس مؤلفه هایشان مرتب می‌شوند. اگر نقاط ورودی از قبل مرتب شده باشند این الگوریتم از formula_13 خواهد بود. منشتر شده در سال ۱۹۸۴ توسط Michael Kallay. اولین الگوریتم بهینه حساس به خروجی که در آن از تکنیک marriage-before-conquest استفاده می‌شود. در سال ۱۹۸۶ توسطKirkpatrick و Seidel انتشار یافت. الگوریتم بهینه و ساده‌تر حساس به خروجی که در سال ۱۹۹۶ توسط Chan کشف شد.
ابتکار ساده‌ای که در ادامهٔ کار می‌آید اغلب اولین مرحله در پیاده‌سازی الگوریتم پوش محدب برای بهبود کارایی آن می‌باشد. پایهٔ آن بر اساس اگوریتمی کارا که در سال ۱۹۷۸ توسطSelim Akl و G.T.Toussaint ارائه شد. ایدهٔ کار به این صورت است که به‌طور سریع نقاطی که به هیچ وجه نمی‌توانند در پوش محدب باشند را حذف کنیم. این روش بر مبنای آن است که در ادامه می‌آید. دو نقطه‌ای را که دارای کمترین و بیشترین مختصات x می‌باشند و به همین ترتیب دو نقطه‌ای که دارای کمترین و بیشترین مختصات y اند را پیدا می‌کنیم.(این کار در formula_13 انجام می‌شود.)این چهار نقطه تشکیل یک چهار ظلعی محدب را می‌دهند و تمام نقاطی که در این چهار ظلعی قرار می‌گیرند (غیر از چهار نقطهٔ ابتدایی) نمی‌توانند درون پوش محدب باشند. پیدا کردن تمامی نقاطی که درون این چهار ظلعی قرار می‌گیرند نیز formula_13 هزینه می‌برد، پس در کل تا اینجا از formula_13 هزینه کرده‌ایم. به‌طور دلخواه نقاط با کمترین و بیشترین مجموع x,y و نقاط با کمترین و بیشترین تفاضل x,y را نیز می‌توانند به چهار ظلعی قبلی اضافه شوند تا این نقاط بر روی هم یک ۸ ظلعی محدب را به وجود آورند که نقاط درون آن به راحتی می‌توانند حذف شوند. اگر نقاط ورودی به صورت رندم انتخاب شوند آنگاه برای کلاسی گسترده از تابع‌های چگالی احتمال، این دور انداختن بعضی از نقاط در پیش پردازش باعث می‌شود که الگوریتمی که اجرا می‌شود دارای پیچیگی زمانی باشد که امید ریاضی آن خطی باشد، حتی اگر در بدترین حالت از formula_23 باشد.
در بحثهای بالا فرض بر آن است که تمامی نقاط از قبل به ما داده شده‌است. اما ممکن است کسی به این دو حالت بپردازد. درج یک نقطه به تعداد ضلع‌های پوش محدب حداکثر یک واحد اضافه می‌کند در حالی که عمل حذف می‌تواند یک پوش سه راسی را به یک پوش n-۱ راسی تبدیل کند.
در نوع برخط با اضافه شدن هر نقطهformula_24 هزینه شده که به‌طور مجانبی بهینه است. در نوع داینامیک هر عملیات درformula_25 انجام می‌شود.
McCallum و Avis اولین نفراتی بودند که پوش محدب برای یک چندظلعی ساده با رأس‌های را درformula_13) ساختند. ایدهٔ اصلی بسیار ساده است. چپترین نقطه روی پوش محدب می‌باشد و ما آن را با formula_27 مشخص می‌کنیم. دومین نقطه را نیز به عنوان کاندیدی برای راس پوش فرض می‌کنیم. در هر مرحله به سه راس متوالی نگاه می‌کنیم که دو تای اول به عنوان رأس‌های موقت پوش اختصاص داده شده‌اند و راس سوم هنوز پردازش نشده‌است که ما آن‌ها را به صورتformula_28 مشخص می‌کنیم. اگر زاویهٔ بین آن‌ها محدب بود انگاه formula_29 و این سه تایی با یک انتقال یک راسی سه تایی بعدی را مشخص می‌کند. اما اگر زاویهٔ ایجاد شده مقعر باشد آنگاه نقطه میانی(formula_30) پاک شده و این تست برای سه تایی formula_31 تا تکرار می‌کنیم تا این که یا به زاویهٔ محدب رسیده یا این که به و بعد از نقطهٔ بعدی به سه تایی برای تست شدن اضافه می‌شود و این روند تکرار می‌شود. هر چند که در تعدادی از مقالاتی که در گذشته انتشار یافته‌اند از امکان خود متقاطع شدن چند ضلعی در حین حذف رءوس صحبت شده که دلیلی بر نامعتبر بودن روند این الگوریتم می‌باشد. خوشبختانه، این مورد نیز به صورت کارا مدیریت می‌شود. بعداً Tor و Middleditch و به صورت مستقل Melkman رویکردی ساده‌تر با پیچیدگی زمانی یکسان ارائه کردند.
شماری از الگوریتم‌ها برای سه بعد وجود دارد، همچنین برای بعدهای دلخواه: نگاه کنید به:https://web.archive.org/web/20070609032115/http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
برای مجموعه‌ای محدود از نقاط در سه بعد پوش محدب به صورت یک چند وجهی محدب می‌باشد یا به‌طور کلی یک چندوجهی محدب برای هر تعداد بعد، که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. نمایش آن به سادگی نمایش در بعد نمی‌باشد. در بعدهای بالاتر حتی اگر رأس‌های این چند وجهی معلوم باشند. ساختن وجههای آن کاری بدیهی نیست. همچنین دوگان این مسئله نیز این چنین است یعنی پیدا کردن رأس‌ها از روی وجه‌ها. سایز خروجی می‌تواند به صورت نمایی از سایز ورودی بیشتر باشد، حتی در شرایطی که سایز خروجی و ورودی قابل مقایسه باشد الگوریتم‌های ارائه شده برای بعدهای بالاتر حساس به خروجی نیستند.