ایالات متحده ورونوی!

برای همه ما پیش می‌آید که برای انجام کاری به اداره پست مراجعه کنیم. حال اگر در اطراف شما چندین اداره پست وجود داشته باشد کدام یک را انتخاب می‌کنید؟

در دنیای علوم کامپیوتر این دسته از مسائل به کمک الگوریتم‌های تقسیم صفحه حل می‌شوند. یکی از معروف‌ترین و پرکاربرد ترین این الگوریتم‌ها، الگوریتم ورونوی (voronoi) است.

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

حال بیایید رو مسئله اداره پست این الگوریتم را پیاده کنیم.

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

حالا مثال دیگری را در نظر بگیرید. فرض کنید صاحب یک غذاخوری زنجیره‌ای تصمیم دارد شعبه‌ی جدیدی در شهر افتتاح کند. چطور محله‌ی مناسبی برای اینکار پیدا کند؟

برای اینکار نیاز است تا محلی را پیدا کند که فاصله‌ی آن تا اولین شعبه غذاخوری بیشینه باشد. برای حل این مسئله دوباره به علوم کامپیوتر مراجعه می‌کنیم.

الگوریتم مثلث بندی دلانی (Delaunay triangulation) یکی از الگوریتم‌هایی است که به کمک نمودار ورونوی قابل پیاده‌سازی است. پس در مرحله اول نمودار ورونوی را رسم می‌کنیم.

شعب غذاخوری نقش گره‌های الگوریتم را بازی می‌کنند و نمودار ورونوی توسط مرز شهری محدود شده است. در مرحله‌ی بعدی هر گره را به گره‌های همسایه‌اش که توسط ورونوی مشخص شده وصل می‌کنیم.

به این ترتیب ما توانستیم مثلث بندی دلانی را روی مسئله پیاده‌سازی کنیم. اما هنوز جواب مسئله پیدا نشده است. برای پیدا کردن پاسخ نهایی نیاز داریم تا از خواص هندسی این الگوریتم استفاده کنیم. همانطور که می‌دانید سه راس هر مثلث بر روی یک دایره قرار می‌گیرند که به آن دایره محیطی گفته می‌شود. اگر دایره محیطی تمام مثلث‌ها را رسم کنیم می‌توانیم دایره‌ای را که شعاع آن بیشینه است پیدا کنیم. مقدار شعاع دایره برابر است با فاصله مرکز دایره تا نقطه‌ای روی محیط دایره (و همینطور شعب غذاخوری!).

بنابراین مرکز دایره‌ای که شعاع بیشینه دارد بهترین مکان برای ساخت شعبه جدید است. چون بیشترین فصله را تا اولین شعبه‌ی غذاخوری زنجیره‌ای (شعاع دایره) دارد.

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

در این نمودار مراکز ایالات به عنوان گره‌ها در نظر گرفته شده‌اند. با اعمال این تغییرات Manhatan در ایالت New Jersy قرار می‌گیرد زیرا به Trenton نزدیک‌تر است تا Albany. یا Chicago در ایالت Wisconsin قرار می‌گیرد زیرا به Madison نزدیکتر است تا Springfield.

دو الگوریتم معرفی شده کاربرد‌های بسیاری دارند و در علوم رباتیک هم استفاده شده‌اند. از نمونه‌های پیاده‌سازی الگوریتم میتوان به بیس agent2d از لیگ شبیه‌سازی دوبعدی فوتبال اشاره کرد. اگر راجع به این لیگ چیزی نمی دانید می‌توانید در مورد آن در ویرگول یا سایت rcss.ir بخوانید.

اگر این نوشته را دوست داشتید و علاقه‌مند هستید بیشتر درباره این موضوعات بخوانید انتشارات KN2C را دنبال کنید و به این صفحه هم سری بزنید.

منبع عکس‌ها : یوتیوب