برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

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