الگوریتم چان

در هندسۀ محاسباتی، الگوریتم چان که به افتخار Timothy M. Chan و پس از او نامگذاری شد، الگوریتمی بهینه و حساس به خروجی است که پوش محدب در مجموعه ای از n نقطه که در فضای دو یا سه بعدی قرار دارند را محاسبه می‌کند.

این الگوریتم از مرتبهٔ (O(n log h زمان می‌گیرد که در آن h، تعداد راس‌های خروجی (پوش محدب) است. در حالت مسطح، این الگوریتم، الگوریتمی از مرتبۀ پیچیدگی (O(n log n (مانند جستجوی گراهام) را با الگوریتم بسته‌بندی هدیه هدیه ترکیب می‌کند تا در زمان بهینۀ O(n logh) اجرا شود.این الگوریتم از آن جهت که بسیار ساده‌تر از الگوریتم نهایی پوش محدب برای سطح است و به‌طور طبیعی هم قابلیت تعمیم به فضای 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+1 گام متوقف کرد. بنابراین اجرای آن تنها به اندازۀ (O(nlog m، البته بدون محاسبۀ پوش محدب، زمان می گیرد. می توانیم در ابتدا، m را ثابت کوچکی در نطر بگیریم و سپس مقدار آنرا افزایش دهیم تا زمانی که m>h شود.در این حالت، پوش محدب به عنوان خروجی بدست می آید.ثابت اولیۀ m را نیز در فرض های خود 2 در نظر می گیریم اما در عمل عددی حدود 5 بهتر عمل می کند.

اگر مقدار m خیلی آرام افزایش یابد، ممکن است الگوریتم مراحل بالا را دفعات زیادی تکرار کند و این باعث می‌شود زمان اجرا بسیار زیاد شود. از طرف دیگر، اگر مقدار m به سرعت افزایش یابد، ممکن است m ناگهان از h خیلی بیشتر شود و این امر خود باعث افزایش زمان اجرا می شود. الگوریتم چان، مقدار m را در هر تکرار مربع می کند و هر بار اطمینان حاصل می کند که مقدار m هیچگاه از n بیشتر نشود.به عبارت دیگر در تکرار tام(که t از صفر شروع می شود)، $m=\min(n,2^{2^{t}})$.

زمان اجرای کل الگوریتم برابر است با:

$\sum _{t=0}^{O(\log \log h)}O\left(n\log(2^{2^{t}})\right)=O(n)\sum _{t=0}^{O(\log \log h)}O(2^{t})=O\left(n\cdot 2^{1+O(\log \log h)}\right)=O(n\log h).$

برای تعمیم این روش به فضای 3 بعدی، باید به جای الگوریتم جستجوی گراهام، از الگوریتم با زمان اجرای (O(n log n برای محاسبۀ پوش محدب در فضای 3 بعدی استفاده شود. همچنین به جای الگوریتم مارش برای بسته بندی هدیه، باید از نسخۀ 3بعدی آن استفاده کنیم. با این تغییرات، پیچیدگی اجرای الگوریتم همچنان (O(n log h باقی می ماند.

پیاده سازی

در مقالۀ چان، روش‌های پیشنهادی زیادی برای بهبود عملی کارایی الگوریتمش آمده است که بعضی از آنها عبارتند از:

• هنگامی که می خواهیم برای یک زیر مجموعه، پوش محدب را حساب کنیم، بهتر است فرض شود که نقاطی را که در پوش محدب نیستند در زیر مجموعه‌ای که الگوریتم بر روی آن اجرا می‌شود هم وجود ندارد.
• در محاسبۀ پوش محدب برای مجموعه‌های بزرگ از نقاط، می‌توان به جای اینکه از ابتدا پوش را محاسبه کرد، از ادغام پوش های محدبی که قبلاً حساب شده استفاده کرد.

منابع

• Timothy M. Chan. "Optimal output-sensitive convex hull algorithms in two and three dimensions". Discrete and Computational Geometry, Vol. 16, pp.361–368. 1996..

جستارهای وابسته

• پوش محدب
• جستجوی دودویی