سال انتشار: ۱۳۸۸

محل انتشار: پانزدهمین کنفرانس بین المللی سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۶

نویسنده(ها):

زاهد رحمتی – دانشکده علوم ریاضی، دانشگاه صنعتی شریف
علیرضا زارعی – دانشکده علوم ریاضی، دانشگاه صنعتی شریف

چکیده:

در این مقاله ما به ارائه ی یک داده ساختار جنبشی کارا وواکنشی برای نگهداری درخت پوشای کمینه اقلیدسی میپردازیم. این داده ساختار در واقع درخت پوشای کمینه اقلیدسی را روی نقاط متحرکی که مسیر حرکت هر کدام از نقاط یک تابع چند جمله ای با درجه ثابت بر حسب زمان است را نگهداری م یکند . اندازه ا ین داده ساختار( O(n2 است و در زمان پیش پردازش ها( O(n2logn ساخته می شود کل تعداد رخدادهایی که در این داده ساختار پردازش می شوند.( O(n4 است که هر رخداد در زمان(O(logn پردازش می شود.