Towards Dynamic Randomized Algorithms in Computational Geometry

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

Computational geometry concerns itself with designing and analyzing algorithms for solving geometric problems. The field has reached a high level of sophistication, and very complicated algorithms have been designed.However, it is also useful to develop more practical algorithms, so long as they are based on rigorous methods. One such method is the use of randomized algorithms. These algorithms have become more and more popular, turning into one of the hottest areas of recent years. Dynamic algorithms are particularly interesting because in practice the data of a problem are often acquired progressively. In this monograph the author studies the theoretical complexity and practical efficiency of randomized dynamic algorithms.