الگوریتم پاک‌سازی خطی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
نمایشی از الگوریتم فورچون که یک تکنیک پاک سازی خطی برای ساخت دیاگرام ورونوی است

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

تاریخچه[ویرایش]

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

کاربردها[ویرایش]

استفاده از این روش در نظریه پیچیدگی محاسباتی الگوریتم های هندسی آن زمان موجب رسیدن به موفقیت شد که Michael Ian Shamos و Hoey الگوریتم ها را برای تقاطع خط در صفحه ارایه کردند و به خصوص توضیح داد که چگونه ترکیبی از روش تفسیر خط با ساختارهای کارآمد داده ها امکان تشخیص تقاطع میان N بخش در صفحه در پیچیدگی زمانی (O (N log N را فراهم میکند. همچنین در نتیجه آن الگوریتم بنتلی-اوتمن از تکنیک پاک سازی خطی برای یافتن تمام k تقاطع میان n بخش در صفحه در پیچیدگی زمانی (O((N + K) log N و فضای پیچیدگی زمانی (O(N استفاده میکند.
از آن به بعد نیز این روش برای طراحی الگوریتم های کارآمد برای تعدادی از مسایل مانند ساختاری از ترسیم دیاگرام ورونوی (الگوریتم فورچون) و مثلث‌بندی دیلانی یا عملیات بولی در چند ضلعی استفاده می شود.

تعمیم و الحاقات[ویرایش]

پاک سازی توپولوژیکی نوعی از پاک سازی های صفحه ای با ترتیبی آرام از نقاط پردازش است که از مرتب سازی برای تمام نقاط جلوگیری می کند و باعث می شود که برخی الگوریتم های پاک سازی خطی به صورت موثرتر انجام گردد.
تکنیک کالیپر های چرخشی برای طراحی الگوریتم های هندسی نیز ممکن است به گونه ای از پاک سازی های صفحه ای تعبیر شود. در هندسه دوگانه تصویری از ورودی صفحه : یکی از گونه های شهودی، شیب یک خط در یک صفحه را تبدیل به مختصات x یک نقطه در یک صفحه دوگانه می کند. بنابراین رسیدن به نتیجه به وسیله خطوط در حالت مرتب شده توسط شیب آنها که با الگوریتم کالیپر چرخشی حاصل میشود در واقع راه دیگری در یافتن جواب به وسیله نقاط مرتب شده با استفاده از مختصات x آنها در الگوریتم پاک سازی صفحه ای می باشد.
روش پاک سازی را نیز ممکن است بتوان به ابعاد بالاتر تعمیم داد.

منابع[ویرایش]

  • ویکی‌پدیای انگلیسی