درخت پوشای کمینه اقلیدسی روی نقاط متحرک

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

Keywords:

هندسه محاسباتی , درخت پوشای کمینه اقلیدسی , داده ساختار جنبشی