نمودار ورنوی
در علم ریاضیات، نمودار ورنوی روشی برای تقسیم فضا به تعدادی ناحیه می‌باشد. در این دیاگرام به هر مجموعه‌ای از نقاط (که دامنه‌ها، سایت‌ها یا ژنراتورها نامیده می‌شوند) ناحیه‌ای اختصاص داده می‌شود. این نواحی سلول‌های ورونوی نامیده می‌شود. برای یک مجموعه از نقاط دیاگرام ورونوی سطح را به مناطقی تقسیم‌بندی می‌کند که برای هر نقطه از مجموعه نقاط یک منطقه تعریف می‌شود. به طوری که تمام نقاط این منطقه به نقطه تولیدکننده آن منطقه نزدیکتر می‌باشد. از کاربردهای این دیاگرام در مثلث بندی دیلانی می‌باشد.
این دیاگرام به افتخار یوهان پتر گوستاف لوژون دیریکله به نام موزاییک کاری دیریکله، و بعد از گریگوری وُرنوی به نام موزاییک کاری وُرُنوی یا تجزیه وُرُنوی نامیده شد. دیاگرام‌های ورونوی در علوم و فناوری‌های متعدد یا حتی در هنر کاربرد دارد و تاکنون کاربردهای متفاوتی از آن در زمینه‌های خاص گزارش شده‌است.
در ساده‌ترین و بارزترین مورد (همان طور که در شکل نشان داده شده‌است) یک مجموعه متناهی از نقاط "formula_1" را در یک فضای اقلیدسی در این مورد هر ناحیه "formula_2" یک نقطه ساده بوده که برای آن سلول ورونوی "formula_3" (که ناحیه ورونوی یا سلول دیریکله نامیده می‌شود.)درنظر می‌گیریم "formula_3" شامل نقاط دیگری نیز می‌باشد که فاصله هر نقطه درون "formula_3" تا "formula_2" کمتر یا برابر با فاصله سایر سایت‌ها تا "formula_2" می‌باشد. این سلول از به اشتراک گذاشتن نیمی از فضا حاصل می‌شود و بنابراین یک چند ضلعی محدب نامیده می‌شود. بخش‌های دیاگرام ورونوی تمامی نقاط سطح می‌باشد که با دو تا از نزدیکترین سایت‌ها هم فاصله می‌باشد. رأس‌های ورونوی (گره‌ها) نقاط هم فاصله با سه (یا تعداد بیشتر) سایت‌ها می‌باشد.
فرض کنید formula_8 یک فضا (مجموعه ناتهی) با تابع فاصله formula_9 باشد. فرض کنید formula_10 یک مجموعه از اندیس‌ها و formula_11 یک چند تایی (مرتب شده) از زیر مجموعه‌های ناتهی (سایت‌ها) در فضای formula_12 باشد. سلول ورونوی یا ناحیه ورونوی formula_13 که متناظر با formula_14 می‌باشد. به طوریکه formula_13 مجموعه‌ای از نقاط در فضای formula_12 می‌باشد که فاصله اشان تا formula_14 کوچکتر یا مساوی سایر نقاط formula_18 می‌باشد جاییکه formula_19 مخالف هر اندیس "k" می‌باشد. به عبارت دیگر اگر formula_20 مشخص‌کننده فاصله بین "x" و زیر مجموعه "A" باشد پس formula_21. نمودار ورونوی یک چندتایی ساده از سلول‌های formula_22 می‌باشد. در اصل بعضی از سایت‌ها می‌توانند از وسط قطع شده و حتی در یک ناحیه قرار گیرند (یک کاربرد آن برای فروشگاه‌ها شرح داده شده‌است.)اما معمولاً فرض بر این است که در یک ناحیه به صورت مجزا قرار گیرند. به علاوه تعداد نامتناهی سایت در این دیاگرام می‌توان تعریف کرد (که کاربرد در هندسه محاسباتی و بلورنگاری می‌باشد.)اما غالباً تعداد متناهی سایت در نظر گرفته می‌شود. در مورد خاص فضا یک فضای اقلیدسی با بعد متناهی می‌باشد، هر سایت یک نقطه بوده که بسیاری از نقاط متناهی در نظر گرفته می‌شوند به طوری که همه آن‌ها متفاوت می‌باشند. پس سلول‌های ورونوی چند وجهی‌های محدب بوده و می‌توان آن‌ها را با روش‌های ترکیبی و با استفاده از رئوس، نمای دو بعدی و... نمایش داد. گاهی اوقات ساختار ترکیبی کاهشی به دیاگرام ورونوی ارجاع داده می‌شود. به هر حال در حالت کلی سلول‌های ورونوی محدب یا پیوسته نمی‌باشد.
به عنوان یک توضیح ساده، مجموعه از فروشگاه‌ها را در یک شهر مسطح در نظر می‌گیریم. فرض کنید که می‌توان تعداد مشتریان فروشگاه را تخمین زد. در نظر می‌گیریم سایر پارامترها (مانند قیمت‌ها، محصولات، کیفیت خدمات و...)ثابت باشد. به طوریکه تنها فاکتور انتخاب فروشگاه توسط مشتریان فاصله تا فروشگاه باشد. بنابراین مشتریان فروشگاهی را انتخاب می‌کنند که از موقعیت آن‌ها حداقل فاصله را داشته باشد. در اینجا سلول ورونوی formula_13 و فروشگاهformula_14 بوده و از نمودار ورونوی می‌توان برای تخمین تعداد مشتریان فروشگاه استفاده نمود (در مدلسازی ما هر فروشگاه در شهر در حقیقت یک نقطه دیاگرام ورونوی می‌باشد.) تا به اینجا فرض بر این بوده که فاصله بین نقاط در شهر به صورت استاندارد اندازه گیری شده‌است که متناظر با فضای اقلیدسی است به طوریکه formula_25. به هر حال اگر ما مسئله را طوری بررسی کنیم که مشتریان تنها با وسیله نقلیه به فروشگاه رفته و مسیرهای ترافیکی به موازات محورهای"X" و "Y" باشد، مانند جزیره منهتن، بنابراین تابع فاصله واقعی فاصله formula_26 خواهد بود که آن را formula_9 می‌نامیم به طوری که formula_28.استفاده غیر رسمی از دیاگرام ورونوی به سال ۱۶۴۴ و توسط دکارت بر می‌گردد.یوهان پتر گوستاف لوژون دیریکله از نمودارهای ورونوی دو و سه بعدی در مطالعات فرم و حالت درجه دو در سال ۱۸۵۰ استفاده کرد. فیزیکدان انگلیسی به نام جان اسنو در سال ۱۸۵۴ از یک نمودار ورونوی استفاده کرد تا بتواند پاسخ مناسبی برای این سؤال پیدا کند که چگونه اکثریت مردم ساکن سوهو که در اثر ابتلا به بیماری وبا جان خود را از دست می‌دهند در نزدیکی پمپ‌های «خیابان ِ برود» زندگی می‌کنند که آلوده به عامل عفونت وبا می‌باشد در صورتی که اقلیت مبتلایان از سایر پمپ‌های آب استفاده می‌نمودند.
دیاگرام ورونوی بعد از ریاضیدان اوکراینی گریگُری ورونوی با این نام شناخته شد. ورونوی در سال ۱۹۰۸ مطالعات خود را بر این دیاگرام در فضای "formula_29" بعدی عمومی انجام داد. دیاگرام ورونوی مورد استفاده در ژئوفیزیک و هواشناسی به منظور آنالیز داده‌های توزیع فضایی (مانند اندازه‌گیری میزان بارش)، بعد از هواشناس آمریکایی Alfredh. Thiessen با نام چند ضلعی Thiessen شناخته شد. در فیزیک مواد متراکم و فشرده مانند موزاییک کاری‌ها به عنوان سلول واحد Wigner-Seitz شناخته می‌شود.موزاییک کاری ورونوی در تکانه شبکه دو طرفه با نام مناطق Brillouin شناخته می‌شود. برای شبکه‌های عمومی در گروه لی این سلول‌ها به صورت ساده با عنوان دامنه اساسی نامیده می‌شوند. در زمینه فضاهای متریک عمومی سلول‌ها غالباً چندضلعی اساسی متریک نامیده می‌شود. سایر نام‌های معادل برای این مفهوم (و یا موارد مهم خاص آن) عبارتند از: چندوجهی ورونوی، چند ضلعی ورونوی، دامنه (های) نفوذ، تجزیه ورونوی، موزاییک کاری (های) ورونوی، موزاییک کاری‌های دیریکله.
موزاییک کاری شبکه‌های منظم در دو یا سه بعد در بسیاری از موزاییک کاری‌های معروف توسعه یافته‌است.
برای مجموعه‌ای از نقاط ("x", "y") با در نظر گرفتن "x" در مجموعه جدا "X" و "y" در مجموعه مجزا "Y" به کاشی مستطیلی شکل خواهیم رسید که لزوماً نقاط در مرکز آن‌ها قرار ندارند.
اگرچه یک سلول ورونوی نرمال به عنوان یک مجموعه از نقاط با نزدیکترین فاصله به یک نقطه تنها در "S" تعریف شده‌اند، یک سلول ورونوی از مرتبه "formula_29" به عنوان یک مجموعه از نقاط نامیده می‌شود که یک مجموعه خاص از "formula_29" در "formula_32" دارند که این "formula_29" نزدیکترین همسایه به نقطه تنهای مورد نظر می‌باشد. دیاگرام ورونی از مرتبه بالاتر هم چنین فضا را طبقه بندی می‌کنند.
دیاگرام ورونوی مرتبه بالاتر می‌توانند به صورت بازگشتی تولید شوند. به منظور تولید نمودار ورونوی از مرتبه "formula_29" از مجموعه "S"با دیاگرام مرتبه "formula_35"ام شروع نموده و هر سلول تولید شده با "formula_36" را با نمودار تولید شده روی مجموعه  "formula_37" جایگزین می‌کنیم.
برای یک مجموعه "formula_29" نقطه‌ای، نمودار ورونوی مرتبه "formula_35" ام دیاگرام ورونوی با نام دیاگرام ورونوی دورترین نقطه شناخته می‌شود.
برای یک مجموعه از نقاط "formula_40" دیاگرام ورونوی دورترین نقطه طرح را به سلول‌هایی تقسیم می‌کند که نقطه یکسان "P" دورترین نقطه می‌باشد. توجه داشته باشید که نقطه "P" دارای سلولی در دیاگرام دورترین نقطه است اگر و تنها اگر به عنوان یک راس از پوشش محدب "P" باشد. بنابراین "formula_41" را به عنوان پوشش محدب "P" قرار داده به طوری که هر نقطه درون "formula_42" با این ویژگی که نقطه "q" در درون سلول مربوط به سایت "formula_43" قرار گرفته‌است، دیاگرام ورونوی نقطه دور را به عنوان بخشی از طرح در سلول‌های "formula_44" تعریف می‌کنیم اگر و تنها اگر فاصلهٔ "formula_45" بیشتر از فاصله "formula_46" باشد و "formula_47" و "formula_48" و فاصله "formula_49" فاصله اقلیدسی بین نقطه "formula_50" و "formula_51" است.
به منظور روشن شدن موضوع توسط تعریف کردن، سلول‌های ورونوی می‌تواند برای متریک‌های غیر از فاصله‌های اقلیدسی (مانند ماهالانوبیس و منهتن. به هر حال در این موارد مرزهای سلول ورونوی می‌تواند نسبت به موارد اقلیدسی پیچیده تر شود. چرا که مکان هندسی هم فاصله برای دو نقطه می‌تواند به زیر فضای هم بعد یک یا دو بعدی تقسیم شود.
یک نمودار ورونوی سنگین تابعی از زوج نقاط است که به منظور تعریف سلول ورونوی، تابع فاصله به وسیله ضرب یا جمع وزن‌های نقاط تولید شده اصلاح می‌شود. در مقابل سلول‌های ورونوی توسط فاصله‌های متریک تعریف می‌شود. در این مورد برخی از سلول‌های ورونوی ممکن است خالی باشند. یک دیاگرام توان نوعی لز دیاگرام ورونوی است که مجموعه‌ای از دایره‌ها توسط فاصله توانی تعریف می‌شوند. این دیاگرام همچنین می‌تواند به عنوان دیاگرام ورونوی سنگین معرفی شود به طوری که یک وزن، از مجموع شعاع هر دایره و توان دوم فاصله از مرکز دایره تعریف می‌شود.
دیاگرام ورونوی "n" نقطه در فضای "d" بعدی، نیازمند فضای ذخیره‌سازی formula_52 می‌باشد. بنابراین دیاگرام ورونوی اغلب برای "formula_53" امکان‌پذیر نمی‌باشد. یک پیشنهاد دیگر استفاده از دیاگرام ورونوی تقریبی است به طوری که اگر سلول‌های ورونوی دارای مرزهای فازی باشند می‌توان از این تقریب استفاده نمود.. پیشنهاد دیگر مربوط به زمانی است که هر سایت یک دایره فازی باشد و در نتیجه سلول‌ها نیز فازی شوند.
سلول‌های ورونوی همچنین با سایر ساختارهای هندسی دیگر مانند محورهای میانی (به طوری که در قطعه بندی تصویر شناسایی ماهیت نوری و سایر کاربردهای محاسباتی دیگر مورد استفاده قرار می‌گیرد.)طرح ریزی مستقیم و نمودارهای نقطه‌ای مرتبط است.
در فیزیک پلیمر دیاگرام ورونوی می‌تواند در نمایش دادن حجم خالی پلیمرها مورد استفاده قرار گیرد.
الگوریتم‌ها موضوعات مرتبط