غلاف محدب: تفاوت میان نسخه‌ها

در ریاضیات، پوشش محدب(Convex hull) یا لفاف محدب مجموعه از نقاط در صفحه اقلیدسی یا فضای اقلیدسی، کوچکترین مجموعه محدبی است که شامل این مجموعه می‌باشد. به عنوان مثال، هنگامی که X یک زیر مجموعه محدود از نقاط در صفحه است، پوشش محدب ممکن است به شکل نواری نشان داده شود که در اطراف X کشیده شده‌است. برای این که تصور بهتری از پوش محدب به دست آورید، نقاط صفحه را مانند میخ‌هایی در نظر بگیرید که به دیوار کوبیده شده‌اند. حال کش تنگی را درنظردر نظر بگیرید که همه میخ‌ها را احاطه کرده‌است. در این صورت پوش محدب نقاط شکلی خواهد بود که کش به خود می‌گیرد.

ما در این قسمت دو الگوریتم برای یافتن پوش محدب مجموعه‌ای از نقاط ارائه خواهیم داد. خروجی هر دوی این [[الگوریتم|الگوریتمها]] رئوس پوش محدب در جهت پادساعتگرد خواهد بود.

مجموعه نقاط ورودی را Q در نظر بگیرید. الگوریتم پیمایش گراهام{{انگلیسی|Grham's Scan}} با در نظر گرفتن یک پشته از نقاط کاندید، پوش محدب را پیدا می‌کند(ما این پشته راs می نامیم). در این روش همه نقاط یک بار در پشته اضافه می‌شوند و نقاطی که بر روی محیط پوش محدب قرار ندارند در نهایت از پشته حذف می‌شوند و در نتیجه در پایان الگوریتم مجموعه نقاطی که در s قرار دارند همان رئوس پوش محدب است.

در این جا نشان می دهیممی‌دهیم که زمان اجرای الگوریتم گراهام از <math>O(nlog n)\,\!</math> است. خط 1 الگوریتم زمان <math>O(n)\,\!</math> را مصرف می‌کند چون یک جستجوی ساده بر روی نقاط است. خط 2 الگوریتم را در صورتی که با الگوریتم [[مرتب‌سازی ادغامی]] پیاده‌سازی کنیم در زمان <math>O(nlog n)\,\!</math> اجرا شود. در قسمت‌های بعد نیز ما فقط با پشته s کار می کنیممی‌کنیم و چون هر نقطه دقیقاً یک بار به پشته اضافه می‌شد و حداکثر یک بار از آن حذف می‌شود پس بقیه کد نیز در زمان <math>O(n)\,\!</math> اجرا می‌شود پس در کل الگوریتم پیمایش گراهام در زمان <math>O(nlog n)\,\!</math> اجرا می‌شود.