ساختمان داده‌های جنبشی

یک بعدی:

مجموعه‌ای از نقاط داریم که روی یک خط حرکت می‌کنند. مینیمم آنها را در هر زمان گزارش کنید.

معادله حرکت نقاط چندجمله‌ای پیوسته با درجه کم (ثابت‌) است که از نظر مرتبه زمانی همان خط می‌شود. پس یک سری خط داریم که می‌خواهم lower envelop آنها را حساب کنیم.

برای این کار از sweep استفاده می‌کنیم. به اندازه‌ی تقاطع‌های این نمودارها رویداد داریم که اینجا می‌دانیم خطی است (در واقع چون پاره‌خط هستند alpha(n).n است). برای پیدا کردن مکان رویدادها یک درخت را به صورت بازگشتی می‌سازیم که ابتدا مجموعه نقاط (خط‌ها) را به دو دسته تقسیم می‌کنیم و مینیمم آنها را حساب می‌کنیم و نقطه‌ی برخورد آن را به دست می‌آوریم. در نتیجه زمان به روز رسانی log^2 n خواهد بود چون ممکن است در یک نقطه همه‌ی زیردرخت‌ها به روز شوند در نتیجه زمان لگاریتمی خواهد بود.

دو بعدی:

می‌خواهیم پوسته‌ی محدب (convex hull) نقاط متحرکی را حساب کنیم که معادله حرکتشان چندجمله‌ای با درجه ثابت (کم) و پیوسته است. اگر معادله حرکت چنین شرطهایی را داشته باشد می‌توان تقاطع دو تا از آنها را در زمان چندجمله‌ای به دست آورد. (زمان را به عنوان یک بعد اضافه می‌کنیم.)

اگر به صورت معمولی sweep را اجرا کنیم زمان آن زیاد می‌شود، به جای آن می‌خواهیم طوری این کار را انجام بدهیم که از مرتبه‌ی تعداد تغییرهای جواب باشد. به چنین الگوریتمی کارا می‌گویند.

می‌خواهیم تعداد رأسهای نمودار حرکت را به دست بیاوریم (که تعداد eventهای sweep است). فرض کردیم که درجه کم است پس تعداد تغییرهای خود نمودار را کنار می‌گذاریم (خط فرض می‌کنیم). که تعداد آنها برابر تعداد رأسهای lower envelope نمودارها است که چون حرکت‌ها دوبعدی هستند (در صفحه هستند) از مرتبه‌ی O(n^(2+delta)) است.

مشابه sweepهای قبلی باید یک درخت نگه داریم که با آن عمل به روز رسانی را انجام بدهیم. اینجا درختی که نگه می‌داریم شامل تغییرات لازم برای الگوریتم (داخلی) و تغییرات واقعی پوسته محدب (خارجی) است. بقیه مثل حالت یک بعدی است. به هر کدام از گره‌های میانی این درخت یک certificate می‌گویند چون به ما می‌گوید که یک رویداد مجاز است.

فضای لازم برای الگوریتم درخت است که فضای O(n) می‌گیرد، چون برگ‌های آن هر کدام یکی از خطوط هستند.