الگوریتم شاموس-هویی

الگوریتم شاموس-هویی (Shamos–Hoey algorithm) گونه‌ای از الگوریتم‌ها است.

روش

۱- نقاط را به دو دسته که هر دسته شامل n/2 نقطه است تقسیم می‌کنیم.

۲- هر زیر مسئله را به صورت بازگشتی حل می‌کنیم و لذا برای هر کدام یک پوسته محدب تولید می‌شود. این دو پوسته را c1 و c2 می‌نامیم.

۳-یک نقطه داخل C1 در نظر گرفته و آن را p می‌نامیم.

۴- اگر p€c2 باشد آنگاه (نقطه pهم داخل c1 و هم داخل c2 است): دو مجموعه از نقاط c1 و c2 حول p که یک نقطه داخلی است مرتب هستند لذا می توان آنها را ادغام کرده و سپس قسمت سوم الگوریتم گراهام را روی آنها اجرا کرد.

۵- اگر p€c2 نباشد آنگاه دو نقطه مماسی از p نسبت به c2 را محاسبه کرده لذا c2 به دو قسمت پوسته داخلی زاویه مماسی و پوسته خارجی زاویه مماسی تقسیم می‌شود. نقاط قسمت داخلی زاویه مماسی از c2 را حذف کرده و لذا نقاط قسمت خارجی قسمت زاویه مماسی از c2 و کل نقاط c1 حول p مرتب هستند با ادغام آنها و اجرای قسمت سوم الگوریتم گراهام می توان پوسته محدب نهایی را تشکیل داد.