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