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

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

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

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

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