الگوریتم چان

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