Concrete and Abstract Voronoi Diagrams

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

The Voronoi diagram of a set of sites is a partition of the plane into regions, one to each site, such that the region of each site contains all points of the plane that are closer to this site than to the other ones. Such partitions are of great importance to computer science and many other fields. The challenge is to compute Voronoi diagrams quickly. The problem is that their structure depends on the notion of distance and the sort of site. In this book the author proposes a unifying approach by introducing abstract Voronoi diagrams. These are based on the concept of bisecting curves, which are required to have some simple properties that are actually possessed by most bisectors of concrete Voronoi diagrams. Abstract Voronoi diagrams can be computed efficiently and there exists a worst-case efficient algorithm of divide-and-conquer type that applies to all abstract Voronoi diagrams satisfying a certain constraint. The author shows that this constraint is fulfilled by the concrete diagrams based on large classes of metrics in the plane.