الگوریتم های حلقوی محدب
الگوریتم هایی که پوسته های محدب را از اشیاء مختلف ایجاد می کنند ، کاربردهای گسترده ای در ریاضیات و علوم رایانه دارند .
در هندسه محاسباتی ، الگوریتم های بی شماری برای محاسبه پوسته محدب یک مجموعه محدود از نقاط با پیچیدگی های مختلف محاسباتی ارائه شده است .
کامپیوتر ابزار بدنه محدب که یک غیر مبهم و کارآمد نمایندگی از شکل محدب مورد نیاز ساخته شده است. پیچیدگی الگوریتم های مربوطه معمولاً بر حسب n ، تعداد نقاط ورودی و گاهی اوقات نیز از نظر ساعت h ، تعداد نقاط موجود در پوسته محدب محاسبه می شود.
فهرست
مورد مسطح [ ویرایش ]
مورد کلی را در نظر بگیرید که ورودی به الگوریتم مجموعه ای از نقاط بدون هماهنگی محدود در یک هواپیمای دکارتی است. یک مورد خاص مهم ، که در آن امتیازها به ترتیب تراوش یک مرز چند ضلعی ساده داده می شود ، بعداً در یک زیربخش جداگانه توضیح داده شده است.
اگر همه نقاط در یک خط قرار نداشته باشند ، بدنه محدب آنها یک چند ضلعی محدب است که رئوس برخی از نقاط در مجموعه ورودی است. متداول ترین آن لیست لیستی است که در امتداد مرز آن در جهت عقربه های ساعت یا خلاف جهت عقربه های ساعت سفارش داده شده است. در بعضی از برنامه ها راحت است که یک چند ضلعی محدب را به عنوان تقاطع مجموعه ای از هواپیماهای نیمه هواپیما نمایش دهید .
محدود به پیچیدگی محاسباتی [ ویرایش ]
برای مجموعه ای محدود از نقاط در هواپیما ، محدودیت پایین در پیچیدگی محاسباتی برای یافتن پوسته محدب نشان داده شده به عنوان چند ضلعی محدب به راحتی نشان داده شده است برای مرتب سازی با استفاده از کاهش زیر . برای مجموعه
حد استاندارد پایین ( n log n ) برای مرتب سازی در مدل درخت تصمیم گیری محاسبات اثبات شده است ، که در آن فقط مقایسه های عددی اما عملیات حسابی انجام نمی شود. با این حال ، در این مدل ، بدنه محدب به هیچ وجه قابل محاسبه نیست. مرتب سازی نیز نیاز به Ω ( N ورود N ) زمان در درخت تصمیم جبری مدل محاسبه، یک مدل است که بیشتر مناسب برای پوش محدب، و در این مدل پوش محدب نیز Ω نیاز ( N ورود N ) زمان. [1] با این حال، در مدل های ریاضی رایانه ای است که اجازه می دهد تعداد به سرعت بیش از مرتب O ( N ورود به سیستمn ) زمان ، به عنوان مثال با استفاده از الگوریتم های مرتب سازی عدد صحیح ، می توان سریع تر محورهای محدب محور محاسبه کرد: الگوریتم اسکن گراهام برای قشرهای محدب شامل یک مرحله مرتب سازی منفرد است که به دنبال آن مقدار خطی کار اضافی انجام می شود.
الگوریتم های حساس به خروجی بهینه [ ویرایش ]
همانطور که در بالا گفته شد ، پیچیدگی یافتن یک قشر محدب به عنوان تابعی از اندازه ورودی n با O ( n log n ) کمتر است. با این حال ، پیچیدگی برخی از الگوریتم های حلقوی محدب می تواند از نظر اندازه ورودی n و اندازه خروجی h (تعداد نقاط موجود در پوسته) مشخص شود. به این الگوریتم ها الگوریتم های حساس به خروجی گفته می شود . آنها ممکن است در مواردی که h = o ( n ) از نظر الگوریتم Θ ( n log n ) کارایی بیشتری داشته باشند از نظر غیرمتعارف کارایی بیشتری داشته باشند .
محدودیت پایین در بدترین حالت زمان اجرای الگوریتم های حلقوی محدب حساس به خروجی به صورت ω ( n log h ) در حالت مسطح تعیین شد. [1] چندین الگوریتم وجود دارد که به این پیچیدگی بهینه زمان دست می یابند . اولین مورد در سال 1986 توسط کرکپاتریک و سییدل معرفی شد (که آن را " الگوریتم نهایی بدنه محدب " نامیدند ). الگوریتم بسیار ساده تری در سال 1996 توسط Chan ساخته شد و الگوریتم Chan نامیده می شود .
الگوریتم ها [ ویرایش ]
الگوریتم های شناخته شده محدب محدب در زیر ذکر شده است ، به تاریخ انتشار اول سفارش داده شده است. پیچیدگی زمانی هر الگوریتم بر حسب تعداد ورودی های n و تعداد نقاط موجود در hull h بیان شده است . توجه داشته باشید که در بدترین حالت ساعت h ممکن است به اندازه n باشد.
- بسته بندی هدایا ، با نام مستعار جارویس - O ( nh )
یکی از ساده ترین (اگرچه در بدترین حالت کارآمدترین زمان نیست) الگوریتم های مسطح. ایجاد شده به طور مستقل توسط Chand & Kapur در سال 1970 و RA Jarvis در 1973. این دارای پیچیدگی زمانی O ( nh ) است که در آن n تعداد نقاط موجود در مجموعه است ، و h تعداد امتیازهای پوسته است. در بدترین حالت پیچیدگی Θ ( n 2 ) است. - اسکن Graham - O ( n log n )
یک الگوریتم کمی پیچیده تر اما بسیار کارآمد تر ، منتشر شده توسط رونالد گراهام در سال 1972. اگر امتیاز از قبل توسط یکی از مختصات یا با زاویه به یک بردار ثابت طبقه بندی شده باشد ، الگوریتم زمان O ( n )طول می کشد. - Quickhull به
طور مستقل در 1977 توسط W. Eddy و در 1978 توسط A. Bykat ساخته شد. درست مانندالگوریتم Quicksort ، پیچیدگی زمانی مورد انتظار O ( n log n ) را دارد ، اما ممکن استدر بدترین حالتبه O ( n 2 )منحرف شود. - تقسیم و تسخیر - الگوریتم O ( n log n )
یکی دیگر ازالگوریتم هایO ( n log n ) ، که در سال 1977 توسط آماده سازی و هنگ منتشر شده است. این الگوریتم برای مورد سه بعدی نیز کاربرد دارد. - زنجیره یکتایی ، الگوریتم با نام مستعار اندرو - O ( n log n )
منتشر شده در 1979 توسط AM اندرو. این الگوریتم می تواند به عنوان نوعی از اسکن گراهام مشاهده شود که نقاط مختلف را از طریق مختصات آنها مرتب سازی می کند. وقتی ورودی قبلاً مرتب شده باشد ، الگوریتم زمان O ( n ) را می گیرد. - الگوریتم حلقوی محدب افزایشی - O ( n log n )
منتشر شده در سال 1984 توسط مایکل کالایی. - الگوریتم Kirkpatrick-Seidel - O ( n log h )
اولین الگوریتم حساس به خروجی مطلوب. این الگوریتم تقسیم و تسخیر را با استفاده از تکنیک ازدواج-قبل از فتح و برنامه نویسی خطی کم بعدی اصلاح می کند . توسط کرکپاتریک و سییدل در سال 1986 منتشر شده است. - الگوریتم Chan - O ( n log h )
یک الگوریتم حساس به خروجی ساده تر ایجاد شده توسط Chan در سال 1996. این بسته بندی هدیه را با اجرای یکالگوریتم O ( n log n ) (مانند اسکن گراهام) در زیر مجموعه های کوچک ورودی ترکیب می کند. .
اکتشافی اکلوزوسن [ ویرایش ]
اکتشافی ساده زیر اغلب به عنوان اولین گام در اجرای الگوریتم های حلقوی محدب برای بهبود عملکرد آنها استفاده می شود. این مبتنی بر الگوریتم کارآمد محدب محدب توسط Selim Akl و GT Toussaint ، 1978 است. ایده این است که به سرعت بسیاری از نکات را که به هر حال بخشی از پوسته محدب نمی شوند ، حذف کرد. این روش بر اساس ایده زیر است. دو نقطه را با کمترین و بالاترین مختصات x و دو نقطه با کمترین و بالاترین مختصات y را پیدا کنید. (هر یک از این عملیات O ( n ) را می گیرد.) این چهار نقطه چهار ضلعی محدب را تشکیل می دهند، و همه نکاتی که در این چهارگوشه نهفته است (به جز چهار راس که ابتدا انتخاب شده اند) جزئی از قشر محدب نیستند. یافتن همه این نکات که در این چهارگوشه نهفته است نیز O ( n ) است ، و بنابراین ، کل عملیات O ( n ) است. در صورت اختیاری ، نقاط با کمترین و بیشترین مقدار مختصات x- و y و همچنین مواردی که کوچکترین و بزرگترین تفاوت مختصات x- و y را دارند نیز می توانند به چهار ضلعی اضافه شوند و بدین ترتیب یک هشت ضلعی محدب نامنظم را تشکیل می دهند ، که طرفین آن می توانند با خیال راحت دور ریخته شود. اگر امتیاز متغیرهای تصادفی باشد ، برای یک کلاس باریک اما معمولاً با توابع تراکم احتمال ، این پرتاب استمرحله قبل از پردازش باعث می شود که یک الگوریتم حلقوی محدب در زمان مورد انتظار خطی اجرا شود ، حتی اگر بدترین حالت پیچیدگی الگوریتم محدب محدب هم درجه در n باشد. [2]
مشکلات پوسته محدب بر روی خط و پویا [ ویرایش ]
بحث بالا این مورد را در نظر می گیرد که همه نقاط ورودی از قبل شناخته شده باشند. ممکن است یکی دو تنظیم دیگر را در نظر بگیرد. [1]
- مشکل حلقوی محدب آنلاین : نقاط ورودی بصورت متوالی یک به یک بدست می آیند. پس از ورود هر نقطه به ورودی ، پوسته محدب برای نقطه دستیابی به دست آمده تا کنون باید بطور کارآمد محاسبه شود.
- تعمیر و نگهداری پوسته محدب پویا : نقاط ورودی ممکن است به صورت متوالی درج یا حذف شوند و بدنه محدب باید بعد از هر عمل درج / حذف به روز شود.
درج یک نقطه ممکن است تعداد شاخک های یک محدب محدب را حداکثر با 1 افزایش دهد ، در حالی که حذف ممکن است یک پوسته محدب محور n را به یک n-1 معکوس تبدیل کند.
نسخه آنلاین ممکن است با O (log n ) در هر نقطه اداره شود ، که از نظر نامتقارن بهینه است. نسخه پویا ممکن است با O (log 2 n ) در هر عملیات اداره شود. [1]
چند ضلعی ساده [ ویرایش ]
مقاله اصلی: پوسته محدب از چند ضلعی ساده
پوسته محدب یک چند ضلعی ساده توسط چند ضلعی به قطعات تقسیم می شود که یکی از آنها چند ضلعی است و بقیه جیب هایی هستند که توسط یک قطعه از مرز چند ضلعی و یک لبه تک شاخ محدود می شوند. اگرچه بسیاری از الگوریتم ها برای مشکل ساخت بدنه محدب یک چند ضلعی ساده منتشر شده اند ، اما اکثر آنها نادرست بوده اند. [3] مک کالوم و آویس اولین الگوریتم صحیح را ارائه دادند. [4] ساده سازی بعدی توسط گراهام و یائو (1983) و لی (1983) تنها از یک ساختار داده پشته استفاده می کند.. الگوریتم آنها چند ضلعی را در جهت عقربه های ساعت طی می کند ، و از سمت چپ ترین محور آن شروع می کند. همانطور که اتفاق می افتد ، یک توالی محدب از مهره ها را روی پشته ذخیره می کند ، مواردی که هنوز مشخص نشده اند که در جیب هستند. در هر مرحله ، الگوریتم مسیری را در امتداد چند ضلعی از بالای پشته تا راس بعدی دنبال می کند که در یکی از دو جیب مجاور بالای پشته قرار ندارد. سپس ، در حالی که دو راس برتر روی پشته به همراه این راس جدید در موقعیت محدب قرار ندارند ، پشته را باز می کند ، قبل از این که در نهایت رأس جدید راس را روی پشته فشار دهید. هنگامی که چرخش در جهت عقربه های ساعت به نقطه شروع می رسد ، الگوریتم ترتیب توالی های پشته را به عنوان بدنه باز می گرداند. [5] [6]
ابعاد بالاتر [ ویرایش ]
تعدادی از الگوریتم ها برای پرونده سه بعدی و همچنین برای ابعاد دلخواه شناخته شده اند. [7] الگوریتم چان برای ابعاد 2 و 3 استفاده می شود و از Quickhull برای محاسبه پوسته محدب در ابعاد بالاتر استفاده می شود. [8]
برای مجموعه های محدودی از نقاط ، پوسته محدب یک چند ضلعی محدب در سه بعد یا به طور کلی یک پلی استوپ محدب برای هر یک از ابعاد است که رئوس های آن برخی از نکات در مجموعه ورودی است. نمایندگی آن به همان اندازه در مورد مسطح ساده نیست. در ابعاد بالاتر ، حتی اگر از رئوس های پلی یپورت محدب نیز مشخص باشد ، ساختن چهره های آن یک کار غیر مهم است ، همانطور که مشکل دوتایی ساخت راس ها با توجه به صورت ها وجود دارد. اندازه اطلاعات صورت خروجی ممکن است از نظر ابعادی بزرگتر از اندازه راس ورودی باشد و حتی در مواردی که ورودی و خروجی هر دو با یک اندازه قابل مقایسه باشند ، الگوریتم های شناخته شده برای بدنه های محدب با ابعاد بالا حساس به خروجی نیستندبه دلیل مشکلاتی با ورودی های انحطاطی و همچنین نتایج میانی پیچیدگی بالا. [9]
منبع
https://en.wikipedia.org/wiki/Convex_hull_algorithms