بخشی از پاورپوینت
اسلاید 1 :
فصل هفتم: دیاگرام ورونویVoronoi Diagram
اسلاید 2 :
به نام خدا
تعاریف و خواص اولیه
ساختن دیاگرام ورونوی
دیاگرام ورونوی پاره خط ها
دیاگرام ورونوی Farthest-Point
اسلاید 3 :
صورت مساله
فرض کنید یک فروشگاه زنجیره ای می خواهد مکان هایی را برای احداث فروشگاه تعیین کند. برای بررسی مناسب بودن محل باید بررسی کرد که فروشگاه جدید چه اندازه می تواند در جلب مشتری موفق باشد. برای این کار باید بتوان ناحیه ای که تحت پوشش هر مرکز خرید قرار می گیرد را تعیین کرد.
اسلاید 4 :
فرضیات مسئله:
قیمت هرکالا در همه جا یکسان است.
هزینه به دست آوردن هر کالا =
قیمت کالا + هزینه حمل کالا از فروشگاه
هزینه حمل کالا از فروشگاه به یک محل با فاصله آنها متناسب است.
مشتریان سعی می کنند هزینه به دست آوردن کالا را مینیمم کنند.
اسلاید 5 :
نزدیکترین فروشگاه
Dirichlet (1850) & Voronoi (1908)
convex hullاز مهمترین و پرکاربردترین ساختار بعد
همه اطلاعات مربوط به فاصله های مجموعه ای از نقطه ها (یا اشیای کلی تر)
اسلاید 6 :
تعريف
دياگرام ورونوي (Vor(p)) :
P :={ p1, p2, .,pn } مجموعه n سايت مجزا در صفحه داريم.
طبق قاعده زير به n سلول تقسيم مي شود:
q/ V(pi ) iff dist(q, pi ) < dist(q, pj ) for each pj / P with j / i.
اسلاید 7 :
ناحیه ورونوی
دياگرام ورونوي
سایت
یال
رأس
دیاگرام
اسلاید 8 :
ساختار دیاگرام ورونوی: 1 سایت
تعداد سایت = 1
تعداد نواحی = 1
تعداد یال = 0
تعداد رئوس = 0
دیاگرام ورونوی یک نقطه، تنها از همان نقطه تشکیل شده است.
اسلاید 9 :
ساختار دیاگرام ورونوی: 2 سایت
تعداد سایت = 2 تعداد یال = 1
تعداد نواحی =2 تعداد رئوس = 0
عمودمنصف پاره خط متصل کننده دو نقطه دیاگرام ورونوی آنها است.
اسلاید 10 :
ساختار دیاگرام ورونوی: 3 سایت
تعداد سایت = 3
تعداد نواحی = 3
تعداد یال = 3
تعداد رئوس = 1
برای سه نقطه غیرهم خط، دیاگرام ورونوی ازسه نیم خط تشکیل شده است. عمودمنصف های ضلع های مثلث دیاگرام ورونوی رأس های آن را شکیل می دهند.
اسلاید 11 :
مشاهده 1-7
نتیجه
دیاگرام ورونوی زیربخش مسطحی است که لبه هایش مستقیم هستند.
سلول دیاگرام ورونوی با حداکثر n - 1 یال و n – 1 رأس محدود می شود.
اسلاید 12 :
قضیه 2-7
P مجموعه n سایت در صفحه داده شدهاست. اگر همه سایتها در خط مستقیم واقع شدهاند پس Vor(P) شامل n-1 خط موازی است. در غیر این صورت، Vor(P) پیوسته است و یالهایش پارهخط یا نیمخط هستند.
اثبات
قسمت اول آسان است.
اسلاید 13 :
یالهای Vor(P) پاره خط یا نیم خط هستند.
Vor(P) متصل است.
اگر همه سایتها در خط مستقیم واقع نشدهاند پس Vor(P) پیوسته است و یالهایش پارهخط یا نیمخط هستند.
اثبات (قسمت دوم):
اسلاید 14 :
قضیه 3-7
برای n≥3، در دیاگرام ورونوی مجموعه n سایت در صفحه تعداد رئوس حداکثر2n-5 و تعداد یالها حداکثر3n-6 است.
اثبات:
سایت ها هم خط باشند:
همه سایت ها درخط مستقیم واقع شده اند.
سایت ها هم خط نباشند:
نتیجه:
میانگین تعداد رئوس سلول های ورونوی کمتر از 6 است.
اسلاید 15 :
بزرگترین دایره خالی
بزرگترين دايره خالي q نسبت به مجموعه نقاط P، بزرگترين دايره خالي با مركز q است كه هيچ نقطه P درون آن نيست.
اسلاید 16 :
تشخيص رئوس و يالهاي دیاگرام ورونوی
اسلاید 17 :
اثبات (قسمت اول)
اسلاید 19 :
اثبات (قسمت دوم)
اسلاید 20 :
دایره های تهی ازسایت (یالها)
