الگوریتم‌های پوش محدب

الگوریتمی که پوش محدب اشیای مختلف را به دست می‌دهد کاربردهای وسیعی در ریاضیات و علوم کامپیوتر دارد. در هندسه محاسباتی، الگوریتم‌های متعددی با پیچیدگی‌های محاسباتی گوناگون برای محاسبه پوش محدب مجموعه‌ای محدود از نقاط مطرح شده‌است. محاسبه پوش محدب به معنی ارائه نمایشی نامبهم و کارا از شکل مطلوب می‌باشد. پیچیدگیهای الگوریتم‌های مربوطه معمولاً بر حسب n، تعداد نقاط ورودی، و h، تعداد نقاط درون پوش محدب، سنجیده می‌شوند.

الگوریتم‌های پوش محدب

حالت دو بعدی

اگر همهٔ نقاط روی یک صفحه نباشند آنگاه پوش محدب حاصلچندظلعی محدبی می‌شود که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. معمولترین نمایش پوشه محدب به صورت لیستی از رأس‌های آن می‌باشد که ترتیب آن بر اساس پیمایشی ساعتگرد یا پادساعتگرد بر روی مرز پوش محدب می‌باشد. در بعضی از کاربردها نمایش این چندظلعی محدب به صورت اشتراک تعدادی نیم صفحه مناسب تر می‌باشد.

کران پایین پیچیدگی محاسباتی

کران پایین محاسباتی برای پیدا کردن پوش محدب و نمایش آن به صورت چند ضلعی محدب، مشابه این کران برای مرتب‌سازی می‌باشد و به سادگی می‌توان این مطلب را با کاهش نشان داد. برای نقاط $x_{1},\dots ,x_{n}$ که می‌خواهیم مرتب کنیم، نقاط $(x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})$ را بر روی صفحه در نظر بگیرید. حال چون این نقاط بر روی سهمی که منحنی محدب است قرار دارند به راحتی می‌توان دید که پیمایش بر روی مرز پوش محدب آن‌ها ترتیب مرتب شدهٔ این اعداد را می‌دهد. به وضوح زمان خطی برای تبدیل اعداد به نقاط و سپس به دست آوردن ترتیب مرتب شده، نیاز می‌باشد. از این رو به دست آوردن پوش محدب n نقطه نمی‌تواند سریعتر از مرتبسازی عمل کند.

کران پایین محاسباتی استاندارد به کمک مدل درخت تصمیم$\Theta (n\log n)$ می‌باشد که البته در این مدل تنها مقایسه انجام می‌شود و نه عملیات محاسباتی. به هر حال پوش محدب در این مدل نمی‌تواند محاسبه شود. مرتب‌سازی در مدلدرخت تصمیم جبری نیز از $\Theta (n\log n)$ می‌باشد که این مدل برای پوش محدب مناسبتر می‌باشد که در این مدل نیز به دست آوردن پوش محدب‌ها زمانی از $\Theta (n\log n)$ می‌خواهد. هر چند در مدل‌هایی که اجازه می‌دهند که اعداد سریعتر از $O(n\log n)$ مرتب شودند، برای نمونه الگوریتم هایinteger sorting، پوش محدب نیز می‌تواند سریعتر محاسبه شود: الگوریتم پیمایش گراهام شامل یک مرحله سادهٔ مرتب‌سازی است که به دنبال مقداری کار اضافه که در زمان خطی انجام می‌شوند امده‌اند.

الگوریتم حساس به خروجی بهینه

همان که در بالا ذکر شد پیچیدگی پیدا کردن پوش محدب به صورت تابعی از تعداد نقاط ورودی $\Theta (n\log n)$ می‌باشد. هر چند که پیچیدگی بعضی از الگوریتم‌های پوش محدب بر حسب سایز ورودی n و سایز خروجی h (تعداد نقاط روی پوش محدب) عنوان می‌شود. این گونه الگورتم‌ها حساس به خروجی نامیده می‌شوند. این الگوریتم‌ها ممکن است به‌طور مجانبی کارا تر از $\Theta (n\log n)$ باشند در حالتی که $h=O(n)$

کران پایین در بدترین حالت زمانی الگوریتم‌های مربوط به پوش محدب حساس به خروجی در حالت دوبعدی $\Theta (n\log n)$می‌باشد.الگوریتم‌های متعددی وجود دارند که این پیچیدگی بهینه را به دست می‌دهند. اولین آن‌ها در سال ۱۹۸۶ توسط Kirkpatrick و Seidel معرفی شد (که آن را الگوریتم نهایی پوش محدب نامیدند.)الگوریتم ساده‌تر توسط Chan در ۱۹۹۶ داده شد که الگوریتم چان نامیده شد.

الگوریتم‌ها

الگوریتم‌های شناخته شدهٔ مربوط به پوش محدب در زیر لیست شده‌اند که آن‌ها را بر اساس اولین تاریخ انتشار مرتب کرده‌ایم. پیچیدگی زمانی این الگوریتم‌ها بر اساس تعداد نقاط ورودی n و تعداد نقاط روی پوش محدب h بیان شده‌اند. توجه شود که در بدترین حالت h ممکن است به بزرگی n باشد.

• بسته‌بندی کادو یا جارویس مارچ(به انگلیسی: Gift wrapping)

یکی از ساده‌ترین (اگر چه مؤثرترین در بدترین حالت نمی‌باشد) الگوریتم‌های صفحه‌ای می‌باشد که به‌طور مستقل توسط Chand و Kapur در ۱۹۹۰ و R.A.Jarvis در ۱۹۷۳ کشف شد. این الگوریتم دارای پیچیدگی زمانی $O(nh)$ می‌باشد و در بدترین حالت این پیچیدگی از مرتبه $\Theta (n^{2})$ است.

• جاروب گراهام

یک الگوریتم با کمی پیچیدگی بیشتر ولی کاراتر که در سال ۱۹۷۲ توسط رونالد گراهام انتشار یافت. اگر نقاط قبلاً بر اساس یکی از مؤلفه‌های مختصاتشان یا بر اساس زاویه با برداری ثابت مرتب شده باشند آنگاه این الگوریتم از $O(n)$ می‌باشد.

• پوش سریع

به‌طور مستقل توسط W.Eddy در ۱۹۷۷ و A.Bykat در ۱۹۷۸ کشف شد. درست مانند مرتب‌سازی سریع به‌طور میانگین از$O(nlog(n))$ است ولی ممکن است در بدترین حالت به $\Theta (nh)=O(n^{2})$ برسد.

• الگوریتم تقسیم و حل - $O(n\log n)$

الگوریتم دیگری از $O(n\log n)$ که در سال ۱۹۷۷ توسطPreparata و Hong انتشار یافت. این اگوریتم برای حالت سه بعدی نیز قابل اجرا می‌باشد.

• زنجیر مونوتون یا الگوریتم اندرو

در سال ۱۹۷۹ توسط A.M.Andrew انتشار یافت. به این الگوریتم می‌توان به دید تغییر شکل یافتهٔ Graham scan نگاه کرد که در آن نقاط بر اساس مؤلفه هایشان مرتب می‌شوند. اگر نقاط ورودی از قبل مرتب شده باشند این الگوریتم از $O(n)$ خواهد بود.

• الگوریتم افزایشی پوش محدب

منشتر شده در سال ۱۹۸۴ توسط Michael Kallay.

• الگورتم نهایی مربوط به پوش محدب $O(n\log n)$

اولین الگوریتم بهینه حساس به خروجی که در آن از تکنیک marriage-before-conquest استفاده می‌شود. در سال ۱۹۸۶ توسطKirkpatrick و Seidel انتشار یافت.

• الگوریتم چن

الگوریتم بهینه و ساده‌تر حساس به خروجی که در سال ۱۹۹۶ توسط Chan کشف شد.

الگوریتم ابتکاری (heuristic) Alk-Toussaint

ابتکار ساده‌ای که در ادامهٔ کار می‌آید اغلب اولین مرحله در پیاده‌سازی الگوریتم پوش محدب برای بهبود کارایی آن می‌باشد. پایهٔ آن بر اساس اگوریتمی کارا که در سال ۱۹۷۸ توسطSelim Akl و G.T.Toussaint ارائه شد. ایدهٔ کار به این صورت است که به‌طور سریع نقاطی که به هیچ وجه نمی‌توانند در پوش محدب باشند را حذف کنیم. این روش بر مبنای آن است که در ادامه می‌آید. دو نقطه‌ای را که دارای کمترین و بیشترین مختصات x می‌باشند و به همین ترتیب دو نقطه‌ای که دارای کمترین و بیشترین مختصات y اند را پیدا می‌کنیم.(این کار در $O(n)$ انجام می‌شود.)این چهار نقطه تشکیل یک چهار ظلعی محدب را می‌دهند و تمام نقاطی که در این چهار ظلعی قرار می‌گیرند (غیر از چهار نقطهٔ ابتدایی) نمی‌توانند درون پوش محدب باشند. پیدا کردن تمامی نقاطی که درون این چهار ظلعی قرار می‌گیرند نیز $O(n)$ هزینه می‌برد، پس در کل تا اینجا از $O(n)$ هزینه کرده‌ایم. به‌طور دلخواه نقاط با کمترین و بیشترین مجموع x,y و نقاط با کمترین و بیشترین تفاضل x,y را نیز می‌توانند به چهار ظلعی قبلی اضافه شوند تا این نقاط بر روی هم یک ۸ ظلعی محدب را به وجود آورند که نقاط درون آن به راحتی می‌توانند حذف شوند. اگر نقاط ورودی به صورت رندم انتخاب شوند آنگاه برای کلاسی گسترده از تابع‌های چگالی احتمال، این دور انداختن بعضی از نقاط در پیش پردازش باعث می‌شود که الگوریتمی که اجرا می‌شود دارای پیچیگی زمانی باشد که امید ریاضی آن خطی باشد، حتی اگر در بدترین حالت از $O(n^{2})$ باشد.

مسئله پوش محدب برخط و داینامیک

در بحثهای بالا فرض بر آن است که تمامی نقاط از قبل به ما داده شده‌است. اما ممکن است کسی به این دو حالت بپردازد.

• مسئله پوش محدب برخط:در این حالت نقاط به‌طور پی در پی به ما داده می‌شود و بعد از دریافت هر نقطه در ورودی پوش محدت باید برای مجموعه نقاط دریافت شده به دست آورده شود، پس باید در این حالت پوش محدت کارا محاسبه شود.
• مسئلهپوش محدب داینامیک:نقاط ورودی به‌طور پی در پی درج یا حذف می‌شوند و پوش محدب پس از هر درج یا حذف باید به روزرسانی شود.

درج یک نقطه به تعداد ضلع‌های پوش محدب حداکثر یک واحد اضافه می‌کند در حالی که عمل حذف می‌تواند یک پوش سه راسی را به یک پوش n-۱ راسی تبدیل کند.

در نوع برخط با اضافه شدن هر نقطه$O(\log n)$ هزینه شده که به‌طور مجانبی بهینه است. در نوع داینامیک هر عملیات در$O(\log ^{2}n)$ انجام می‌شود.

به دست آوردن پوش محدب چندضلعی ساده

McCallum و Avis اولین نفراتی بودند که پوش محدب برای یک چندظلعی ساده با رأس‌های را در$O(n)$) ساختند. ایدهٔ اصلی بسیار ساده است. چپترین نقطه روی پوش محدب می‌باشد و ما آن را با $h_{1}$ مشخص می‌کنیم. دومین نقطه را نیز به عنوان کاندیدی برای راس پوش فرض می‌کنیم. در هر مرحله به سه راس متوالی نگاه می‌کنیم که دو تای اول به عنوان رأس‌های موقت پوش اختصاص داده شده‌اند و راس سوم هنوز پردازش نشده‌است که ما آن‌ها را به صورت$h_{k-1},h_{k},v_{i}$ مشخص می‌کنیم. اگر زاویهٔ بین آن‌ها محدب بود انگاه $h_{k+1}=v_{i}$ و این سه تایی با یک انتقال یک راسی سه تایی بعدی را مشخص می‌کند. اما اگر زاویهٔ ایجاد شده مقعر باشد آنگاه نقطه میانی($h_{k}$) پاک شده و این تست برای سه تایی $h_{k-2},h_{k-1},v_{i}$ تا تکرار می‌کنیم تا این که یا به زاویهٔ محدب رسیده یا این که به و بعد از نقطهٔ بعدی به سه تایی برای تست شدن اضافه می‌شود و این روند تکرار می‌شود. هر چند که در تعدادی از مقالاتی که در گذشته انتشار یافته‌اند از امکان خود متقاطع شدن چند ضلعی در حین حذف رءوس صحبت شده که دلیلی بر نامعتبر بودن روند این الگوریتم می‌باشد. خوشبختانه، این مورد نیز به صورت کارا مدیریت می‌شود. بعداً Tor و Middleditch و به صورت مستقل Melkman رویکردی ساده‌تر با پیچیدگی زمانی یکسان ارائه کردند.

بعدهای بالاتر

شماری از الگوریتم‌ها برای سه بعد وجود دارد، همچنین برای بعدهای دلخواه: نگاه کنید به:https://web.archive.org/web/20070609032115/http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

برای مجموعه‌ای محدود از نقاط در سه بعد پوش محدب به صورت یک چند وجهی محدب می‌باشد یا به‌طور کلی یک چندوجهی محدب برای هر تعداد بعد، که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. نمایش آن به سادگی نمایش در بعد نمی‌باشد. در بعدهای بالاتر حتی اگر رأس‌های این چند وجهی معلوم باشند. ساختن وجههای آن کاری بدیهی نیست. همچنین دوگان این مسئله نیز این چنین است یعنی پیدا کردن رأس‌ها از روی وجه‌ها. سایز خروجی می‌تواند به صورت نمایی از سایز ورودی بیشتر باشد، حتی در شرایطی که سایز خروجی و ورودی قابل مقایسه باشد الگوریتم‌های ارائه شده برای بعدهای بالاتر حساس به خروجی نیستند.

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

• Orthogonal convex hull

مطالعه بیشتر

• توماس اچ کورمن, Charles E. Leiserson, رونالد ریوست, and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 33.3: Finding the convex hull, pp.  ۹۴۷–۹۵۷.
• Franco P. Preparata, S.J. Hong. Convex Hulls of Finite Sets of Points in Two and Three Dimensions, Commun. ACM, vol. ۲۰, no. ۲, pp.  ۸۷–۹۳, ۱۹۷۷.
• Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (۲۰۰۰). Computational Geometry (ویراست ۲nd revised edition). اشپرینگر ساینس+بیزینس مدیا. ISBN 3-540-65620-0.نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (رده) نگهداری یادکرد:متن اضافی (رده) Section 1.1: An Example: Convex Hulls (describes classical algorithms for 2-dimensional convex hulls). Chapter 11: Convex Hulls: pp.  ۲۳۵–۲۵0 (describes a randomized algorithm for 3-dimensional convex hulls due to Clarkson and Shor).

پیوند به بیرون

• Weisstein, Eric W. "Convex Hull". MathWorld.
• 2D, 3D, and dD Convex Hull in CGAL, the Computational Geometry Algorithms Library
• Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection
• Demo as Flash swf, Jarvis, Graham, Quick (divide and conquer) and Chan algorithms
• Gift wrapping algorithm in C#