موضوع مقاله: الگوریتم چان | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم چان | مقدمه: Chan و پس از او نامگذاری شد، الگوریتمی بهینه و حساس به خروجی است که پوش محدب در مجموعه ای از n نقطه که در فضای دو یا سه بعدی قرار دارند را محاسبه می‌کند. | ## بخش 1: الگوریتم چان | این الگوریتم از مرتبهٔ (O(n log h زمان می‌گیرد که در آن h، تعداد راس‌های خروجی (پوش محدب) است. در حالت مسطح، این الگوریتم، الگوریتمی از مرتبۀ پیچیدگی (O(n log n (مانند جستجوی گراهام) را با الگوریتم بسته‌بندی هدیه هدیه ترکیب می‌کند تا در زمان بهینۀ اجرا شود.این الگوریتم از آن جهت که بسیار ساده‌تر از الگوریتم نهایی پوش محدب برای سطح است و به‌طور طبیعی هم قابلیت تعمیم به فضای 3 بعدی را دارد، مورد توجه قرار گرفته‌است. الگوریتم در ابتدا فرض می کنیم که عدد h را داریم و بنابراین پارامتر m را برابر h تعریف می کنیم. این فرض شاید به نظر واقعی نرسد، اما بعداً این فرض را از الگوریتم حذف خواهیم کرد.این الگوریتم در ابتدا با تقسیم دلخواه مجموعۀ نقاط(P) به حداکثر 1+n/m زیر مجموعه که در هر یک از آن‌ها حداکثر m نقطه وجود دارد، شروع می‌شود. همچنین برای افزایش سرعت اجرا، در این مرحله از مقادیر از پیش محاسبه شدۀ پوش‌های محدب استفاده می‌شود. در هر گام از اجرای الگوریتم بسته بندی، نقطه‌ای مانند pi در پوش محدب فرض می‌شود و الگوریتم به دنبال این است که نقطه ای مانند (pi+1 = f(pi,P پیدا کند با این ویژگی که بقیۀ نقاط در P، در سمت راست خط گذرنده از pi وpi+1 قرار گیرند. | ## بخش 2: الگوریتم چان | اما این کار فقط نقاطی را در نطر می گیرد که زیر مجموعه‌ای مانند Qاز P وجود داشته باشد که برای آن نقطه (f(pi,Q را حساب کرده باشد. با اجرای دو مرحلۀ اول الگوریتم مطابق آنچه در بالا توصیف شد، می توان پوش محدب را برای n نقطه، با این فرض که مقدار h از قبل مشخص است، در زمان (O(n logh محاسبه کرد. بنابراین اجرای آن تنها به اندازۀ (O(nlog m، البته بدون محاسبۀ پوش محدب، زمان می گیرد. می توانیم در ابتدا، m را ثابت کوچکی در نطر بگیریم و سپس مقدار آنرا افزایش دهیم تا زمانی که m>h شود.در این حالت، پوش محدب به عنوان خروجی بدست می آید.ثابت اولیۀ m را نیز در فرض های خود 2 در نظر می گیریم اما در عمل عددی حدود 5 بهتر عمل می کند. اگر مقدار m خیلی آرام افزایش یابد، ممکن است الگوریتم مراحل بالا را دفعات زیادی تکرار کند و این باعث می‌شود زمان اجرا بسیار زیاد شود. از طرف دیگر، اگر مقدار m به سرعت افزایش یابد، ممکن است m ناگهان از h خیلی بیشتر شود و این امر خود باعث افزایش زمان اجرا می شود. | ## بخش 3: الگوریتم چان | الگوریتم چان، مقدار m را در هر تکرار مربع می کند و هر بار اطمینان حاصل می کند که مقدار m هیچگاه از n بیشتر نشود.به عبارت دیگر در تکرار tام(که t از صفر شروع می شود)، . زمان اجرای کل الگوریتم برابر است با: برای تعمیم این روش به فضای 3 بعدی، باید به جای الگوریتم جستجوی گراهام، از الگوریتم با زمان اجرای (O(n log n برای محاسبۀ پوش محدب در فضای 3 بعدی استفاده شود. همچنین به جای الگوریتم مارش برای بسته بندی هدیه، باید از نسخۀ 3بعدی آن استفاده کنیم. پیاده سازی در مقالۀ چان، روش‌های پیشنهادی زیادی برای بهبود عملی کارایی الگوریتمش آمده است که بعضی از آنها عبارتند از: هنگامی که می خواهیم برای یک زیر مجموعه، پوش محدب را حساب کنیم، بهتر است فرض شود که نقاطی را که در پوش محدب نیستند در زیر مجموعه‌ای که الگوریتم بر روی آن اجرا می‌شود هم وجود ندارد. | ## جمع‌بندی | در محاسبۀ پوش محدب برای مجموعه‌های بزرگ از نقاط، می‌توان به جای اینکه از ابتدا پوش را محاسبه کرد، از ادغام پوش های محدبی که قبلاً حساب شده استفاده کرد.