در علم ریاضیات، نمودار ورنوی روشی برای تقسیم فضا به تعدادی ناحیه می باشد. در این دیاگرام به هر مجموعه ای از نقاط ( که دامنه ها، سایت ها یا ژنراتورها نامیده می شوند ) ناحیه ای اختصاص داده می شود. این نواحی سلول های ورونوی نامیده می شود. برای یک مجموعه از نقاط دیاگرام ورونوی سطح را به مناطقی تقسیم بندی می کند که برای هر نقطه از مجموعه نقاط یک منطقه تعریف می شود. به طوری که تمام نقاط این منطقه به نقطه تولیدکننده آن منطقه نزدیکتر می باشد. از کاربردهای این دیاگرام در مثلث بندی دیلانی می باشد.
این دیاگرام به افتخار یوهان پتر گوستاف لوژون دیریکله به نام موزاییک کاری دیریکله، و بعد از گریگوری وُرنوی به نام موزاییک کاری وُرُنوی یا تجزیه وُرُنوی نامیده شد. دیاگرام های ورونوی در علوم و فناوری های متعدد یا حتی در هنر کاربرد دارد و تاکنون کاربردهای متفاوتی از آن در زمینه های خاص گزارش شده است. [ ۱] [ ۲]
در ساده ترین و بارزترین مورد ( همان طور که در شکل نشان داده شده است ) یک مجموعه متناهی از نقاط { p 1 , p 2 ⋯ , p n } را در یک فضای اقلیدسی در این مورد هر ناحیه p k یک نقطه ساده بوده که برای آن سلول ورونوی R k ( که ناحیه ورونوی یا سلول دیریکله نامیده می شود. ) درنظر می گیریم R k شامل نقاط دیگری نیز می باشد که فاصله هر نقطه درون R k تا p k کمتر یا برابر با فاصله سایر سایت ها تا p k می باشد. این سلول از به اشتراک گذاشتن نیمی از فضا حاصل می شود و بنابراین یک چند ضلعی محدب نامیده می شود. بخش های دیاگرام ورونوی تمامی نقاط سطح می باشد که با دو تا از نزدیکترین سایت ها هم فاصله می باشد. رأس های ورونوی ( گره ها ) نقاط هم فاصله با سه ( یا تعداد بیشتر ) سایت ها می باشد.
فرض کنید X یک فضا ( مجموعه ناتهی ) با تابع فاصله d باشد. فرض کنید K یک مجموعه از اندیس ها و ( P k ) k ∈ K یک چند تایی ( مرتب شده ) از زیر مجموعه های ناتهی ( سایت ها ) در فضای X باشد. سلول ورونوی یا ناحیه ورونوی R k که متناظر با P k می باشد. به طوریکه R k مجموعه ای از نقاط در فضای X می باشد که فاصله اشان تا P k کوچکتر یا مساوی سایر نقاط P j می باشد جاییکه j مخالف هر اندیس k می باشد. به عبارت دیگر اگر d ( x , A ) = inf { d ( x , a ) | a ∈ A } مشخص کننده فاصله بین x و زیر مجموعه A باشد پس R k = { x ∈ X | d ( x , P k ) ≤ d ( x , P j ) for all j ≠ k } . . نمودار ورونوی یک چندتایی ساده از سلول های ( R k ) k ∈ K می باشد. در اصل بعضی از سایت ها می توانند از وسط قطع شده و حتی در یک ناحیه قرار گیرند ( یک کاربرد آن برای فروشگاه ها شرح داده شده است. ) اما معمولاً فرض بر این است که در یک ناحیه به صورت مجزا قرار گیرند. به علاوه تعداد نامتناهی سایت در این دیاگرام می توان تعریف کرد ( که کاربرد در هندسه محاسباتی و بلورنگاری می باشد. ) اما غالباً تعداد متناهی سایت در نظر گرفته می شود. در مورد خاص فضا یک فضای اقلیدسی با بعد متناهی می باشد، هر سایت یک نقطه بوده که بسیاری از نقاط متناهی در نظر گرفته می شوند به طوری که همه آن ها متفاوت می باشند. پس سلول های ورونوی چند وجهی های محدب بوده و می توان آن ها را با روش های ترکیبی و با استفاده از رئوس، نمای دو بعدی و. . . نمایش داد. گاهی اوقات ساختار ترکیبی کاهشی به دیاگرام ورونوی ارجاع داده می شود. به هر حال در حالت کلی سلول های ورونوی محدب یا پیوسته نمی باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین دیاگرام به افتخار یوهان پتر گوستاف لوژون دیریکله به نام موزاییک کاری دیریکله، و بعد از گریگوری وُرنوی به نام موزاییک کاری وُرُنوی یا تجزیه وُرُنوی نامیده شد. دیاگرام های ورونوی در علوم و فناوری های متعدد یا حتی در هنر کاربرد دارد و تاکنون کاربردهای متفاوتی از آن در زمینه های خاص گزارش شده است. [ ۱] [ ۲]
در ساده ترین و بارزترین مورد ( همان طور که در شکل نشان داده شده است ) یک مجموعه متناهی از نقاط { p 1 , p 2 ⋯ , p n } را در یک فضای اقلیدسی در این مورد هر ناحیه p k یک نقطه ساده بوده که برای آن سلول ورونوی R k ( که ناحیه ورونوی یا سلول دیریکله نامیده می شود. ) درنظر می گیریم R k شامل نقاط دیگری نیز می باشد که فاصله هر نقطه درون R k تا p k کمتر یا برابر با فاصله سایر سایت ها تا p k می باشد. این سلول از به اشتراک گذاشتن نیمی از فضا حاصل می شود و بنابراین یک چند ضلعی محدب نامیده می شود. بخش های دیاگرام ورونوی تمامی نقاط سطح می باشد که با دو تا از نزدیکترین سایت ها هم فاصله می باشد. رأس های ورونوی ( گره ها ) نقاط هم فاصله با سه ( یا تعداد بیشتر ) سایت ها می باشد.
فرض کنید X یک فضا ( مجموعه ناتهی ) با تابع فاصله d باشد. فرض کنید K یک مجموعه از اندیس ها و ( P k ) k ∈ K یک چند تایی ( مرتب شده ) از زیر مجموعه های ناتهی ( سایت ها ) در فضای X باشد. سلول ورونوی یا ناحیه ورونوی R k که متناظر با P k می باشد. به طوریکه R k مجموعه ای از نقاط در فضای X می باشد که فاصله اشان تا P k کوچکتر یا مساوی سایر نقاط P j می باشد جاییکه j مخالف هر اندیس k می باشد. به عبارت دیگر اگر d ( x , A ) = inf { d ( x , a ) | a ∈ A } مشخص کننده فاصله بین x و زیر مجموعه A باشد پس R k = { x ∈ X | d ( x , P k ) ≤ d ( x , P j ) for all j ≠ k } . . نمودار ورونوی یک چندتایی ساده از سلول های ( R k ) k ∈ K می باشد. در اصل بعضی از سایت ها می توانند از وسط قطع شده و حتی در یک ناحیه قرار گیرند ( یک کاربرد آن برای فروشگاه ها شرح داده شده است. ) اما معمولاً فرض بر این است که در یک ناحیه به صورت مجزا قرار گیرند. به علاوه تعداد نامتناهی سایت در این دیاگرام می توان تعریف کرد ( که کاربرد در هندسه محاسباتی و بلورنگاری می باشد. ) اما غالباً تعداد متناهی سایت در نظر گرفته می شود. در مورد خاص فضا یک فضای اقلیدسی با بعد متناهی می باشد، هر سایت یک نقطه بوده که بسیاری از نقاط متناهی در نظر گرفته می شوند به طوری که همه آن ها متفاوت می باشند. پس سلول های ورونوی چند وجهی های محدب بوده و می توان آن ها را با روش های ترکیبی و با استفاده از رئوس، نمای دو بعدی و. . . نمایش داد. گاهی اوقات ساختار ترکیبی کاهشی به دیاگرام ورونوی ارجاع داده می شود. به هر حال در حالت کلی سلول های ورونوی محدب یا پیوسته نمی باشد.
wiki: نمودار ورنوی