موضوع مقاله: الگوریتم‌های پوش محدب | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم‌های پوش محدب | مقدمه: در هندسه محاسباتی، الگوریتم‌های متعددی با پیچیدگی‌های محاسباتی گوناگون برای محاسبه پوش محدب مجموعه‌ای محدود از نقاط مطرح شده‌است. | ## بخش 1: الگوریتم‌های پوش محدب | پیچیدگیهای الگوریتم‌های مربوطه معمولاً بر حسب n، تعداد نقاط ورودی، و h، تعداد نقاط درون پوش محدب، سنجیده می‌شوند. حالت دو بعدی اگر همهٔ نقاط روی یک صفحه نباشند آنگاه پوش محدب حاصلچندظلعی محدبی می‌شود که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. معمولترین نمایش پوشه محدب به صورت لیستی از رأس‌های آن می‌باشد که ترتیب آن بر اساس پیمایشی ساعتگرد یا پادساعتگرد بر روی مرز پوش محدب می‌باشد. در بعضی از کاربردها نمایش این چندظلعی محدب به صورت اشتراک تعدادی نیم صفحه مناسب تر می‌باشد. کران پایین پیچیدگی محاسباتی کران پایین محاسباتی برای پیدا کردن پوش محدب و نمایش آن به صورت چند ضلعی محدب، مشابه این کران برای مرتب‌سازی می‌باشد و به سادگی می‌توان این مطلب را با کاهش نشان داد. حال چون این نقاط بر روی سهمی که منحنی محدب است قرار دارند به راحتی می‌توان دید که پیمایش بر روی مرز پوش محدب آن‌ها ترتیب مرتب شدهٔ این اعداد را می‌دهد. به وضوح زمان خطی برای تبدیل اعداد به نقاط و سپس به دست آوردن ترتیب مرتب شده، نیاز می‌باشد. کران پایین محاسباتی استاندارد به کمک مدل درخت تصمیم می‌باشد که البته در این مدل تنها مقایسه انجام می‌شود و نه عملیات محاسباتی. الگوریتم حساس به خروجی بهینه همان که در بالا ذکر شد پیچیدگی پیدا کردن پوش محدب به صورت تابعی از تعداد نقاط ورودی می‌باشد. هر چند که پیچیدگی بعضی از الگوریتم‌های پوش محدب بر حسب سایز ورودی n و سایز خروجی h (تعداد نقاط روی پوش محدب) عنوان می‌شود. این الگوریتم‌ها ممکن است به‌طور مجانبی کارا تر از باشند در حالتی که کران پایین در بدترین حالت زمانی الگوریتم‌های مربوط به پوش محدب حساس به خروجی در حالت دوبعدی می‌باشد.الگوریتم‌های متعددی وجود دارند که این پیچیدگی بهینه را به دست می‌دهند. | ## بخش 2: الگوریتم‌های پوش محدب | الگوریتم‌ها الگوریتم‌های شناخته شدهٔ مربوط به پوش محدب در زیر لیست شده‌اند که آن‌ها را بر اساس اولین تاریخ انتشار مرتب کرده‌ایم. پیچیدگی زمانی این الگوریتم‌ها بر اساس تعداد نقاط ورودی n و تعداد نقاط روی پوش محدب h بیان شده‌اند. این الگوریتم دارای پیچیدگی زمانی می‌باشد و در بدترین حالت این پیچیدگی از مرتبه است. جاروب گراهام یک الگوریتم با کمی پیچیدگی بیشتر ولی کاراتر که در سال ۱۹۷۲ توسط رونالد گراهام انتشار یافت. اگر نقاط قبلاً بر اساس یکی از مؤلفه‌های مختصاتشان یا بر اساس زاویه با برداری ثابت مرتب شده باشند آنگاه این الگوریتم از می‌باشد. درست مانند مرتب‌سازی سریع به‌طور میانگین از است ولی ممکن است در بدترین حالت به برسد. الگوریتم چن الگوریتم بهینه و ساده‌تر حساس به خروجی که در سال ۱۹۹۶ توسط Chan کشف شد. ایدهٔ کار به این صورت است که به‌طور سریع نقاطی که به هیچ وجه نمی‌توانند در پوش محدب باشند را حذف کنیم. دو نقطه‌ای را که دارای کمترین و بیشترین مختصات x می‌باشند و به همین ترتیب دو نقطه‌ای که دارای کمترین و بیشترین مختصات y اند را پیدا می‌کنیم.(این کار در انجام می‌شود.)این چهار نقطه تشکیل یک چهار ظلعی محدب را می‌دهند و تمام نقاطی که در این چهار ظلعی قرار می‌گیرند (غیر از چهار نقطهٔ ابتدایی) نمی‌توانند درون پوش محدب باشند. پیدا کردن تمامی نقاطی که درون این چهار ظلعی قرار می‌گیرند نیز هزینه می‌برد، پس در کل تا اینجا از هزینه کرده‌ایم. به‌طور دلخواه نقاط با کمترین و بیشترین مجموع x,y و نقاط با کمترین و بیشترین تفاضل x,y را نیز می‌توانند به چهار ظلعی قبلی اضافه شوند تا این نقاط بر روی هم یک ۸ ظلعی محدب را به وجود آورند که نقاط درون آن به راحتی می‌توانند حذف شوند. | ## بخش 3: الگوریتم‌های پوش محدب | مسئله پوش محدب برخط و داینامیک در بحثهای بالا فرض بر آن است که تمامی نقاط از قبل به ما داده شده‌است. مسئله پوش محدب برخط:در این حالت نقاط به‌طور پی در پی به ما داده می‌شود و بعد از دریافت هر نقطه در ورودی پوش محدت باید برای مجموعه نقاط دریافت شده به دست آورده شود، پس باید در این حالت پوش محدت کارا محاسبه شود. مسئلهپوش محدب داینامیک:نقاط ورودی به‌طور پی در پی درج یا حذف می‌شوند و پوش محدب پس از هر درج یا حذف باید به روزرسانی شود. درج یک نقطه به تعداد ضلع‌های پوش محدب حداکثر یک واحد اضافه می‌کند در حالی که عمل حذف می‌تواند یک پوش سه راسی را به یک پوش n-۱ راسی تبدیل کند. در هر مرحله به سه راس متوالی نگاه می‌کنیم که دو تای اول به عنوان رأس‌های موقت پوش اختصاص داده شده‌اند و راس سوم هنوز پردازش نشده‌است که ما آن‌ها را به صورت مشخص می‌کنیم. اگر زاویهٔ بین آن‌ها محدب بود انگاه و این سه تایی با یک انتقال یک راسی سه تایی بعدی را مشخص می‌کند. اما اگر زاویهٔ ایجاد شده مقعر باشد آنگاه نقطه میانی پاک شده و این تست برای سه تایی تا تکرار می‌کنیم تا این که یا به زاویهٔ محدب رسیده یا این که به و بعد از نقطهٔ بعدی به سه تایی برای تست شدن اضافه می‌شود و این روند تکرار می‌شود. هر چند که در تعدادی از مقالاتی که در گذشته انتشار یافته‌اند از امکان خود متقاطع شدن چند ضلعی در حین حذف رءوس صحبت شده که دلیلی بر نامعتبر بودن روند این الگوریتم می‌باشد. بعدهای بالاتر شماری از الگوریتم‌ها برای سه بعد وجود دارد، همچنین برای بعدهای دلخواه: نگاه کنید به: برای مجموعه‌ای محدود از نقاط در سه بعد پوش محدب به صورت یک چند وجهی محدب می‌باشد یا به‌طور کلی یک چندوجهی محدب برای هر تعداد بعد، که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. | ## جمع‌بندی | سایز خروجی می‌تواند به صورت نمایی از سایز ورودی بیشتر باشد، حتی در شرایطی که سایز خروجی و ورودی قابل مقایسه باشد الگوریتم‌های ارائه شده برای بعدهای بالاتر حساس به خروجی نیستند.