موضوع مقاله: نمودار ورنوی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نمودار ورنوی | مقدمه: در این دیاگرام به هر مجموعه‌ای از نقاط (که دامنه‌ها، سایت‌ها یا ژنراتورها نامیده می‌شوند) ناحیه‌ای اختصاص داده می‌شود. | ## بخش 1: نمودار ورنوی | برای یک مجموعه از نقاط دیاگرام ورونوی سطح را به مناطقی تقسیم‌بندی می‌کند که برای هر نقطه از مجموعه نقاط یک منطقه تعریف می‌شود. این دیاگرام به افتخار یوهان پتر گوستاف لوژون دیریکله به نام موزاییک کاری دیریکله، و بعد از گریگوری وُرنوی به نام موزاییک کاری وُرُنوی یا تجزیه وُرُنوی نامیده شد. John Wiley, 2000, 671 pages ساده ترین مورد در ساده‌ترین و بارزترین مورد (همان طور که در شکل نشان داده شده‌است) یک مجموعه متناهی از نقاط را در یک فضای اقلیدسی در این مورد هر ناحیه یک نقطه ساده بوده که برای آن سلول ورونوی (که ناحیه ورونوی یا سلول دیریکله نامیده می‌شود.)درنظر می‌گیریم شامل نقاط دیگری نیز می‌باشد که فاصله هر نقطه درون تا کمتر یا برابر با فاصله سایر سایت‌ها تا می‌باشد. این سلول از به اشتراک گذاشتن نیمی از فضا حاصل می‌شود و بنابراین یک چند ضلعی محدب نامیده می‌شود. بخش‌های دیاگرام ورونوی تمامی نقاط سطح می‌باشد که با دو تا از نزدیکترین سایت‌ها هم فاصله می‌باشد. فرض کنید یک مجموعه از اندیس‌ها و یک چند تایی (مرتب شده) از زیر مجموعه‌های ناتهی (سایت‌ها) در فضای باشد. به طوریکه مجموعه‌ای از نقاط در فضای می‌باشد که فاصله اشان تا کوچکتر یا مساوی سایر نقاط می‌باشد جاییکه مخالف هر اندیس k می‌باشد. در اصل بعضی از سایت‌ها می‌توانند از وسط قطع شده و حتی در یک ناحیه قرار گیرند (یک کاربرد آن برای فروشگاه‌ها شرح داده شده‌است.)اما معمولاً فرض بر این است که در یک ناحیه به صورت مجزا قرار گیرند. به علاوه تعداد نامتناهی سایت در این دیاگرام می‌توان تعریف کرد (که کاربرد در هندسه محاسباتی و بلورنگاری می‌باشد.)اما غالباً تعداد متناهی سایت در نظر گرفته می‌شود. در مورد خاص فضا یک فضای اقلیدسی با بعد متناهی می‌باشد، هر سایت یک نقطه بوده که بسیاری از نقاط متناهی در نظر گرفته می‌شوند به طوری که همه آن‌ها متفاوت می‌باشند. پس سلول‌های ورونوی چند وجهی‌های محدب بوده و می‌توان آن‌ها را با روش‌های ترکیبی و با استفاده از رئوس، نمای دو بعدی و... توضیحات به عنوان یک توضیح ساده، مجموعه از فروشگاه‌ها را در یک شهر مسطح در نظر می‌گیریم. در نظر می‌گیریم سایر پارامترها (مانند قیمت‌ها، محصولات، کیفیت خدمات و...)ثابت باشد. بنابراین مشتریان فروشگاهی را انتخاب می‌کنند که از موقعیت آن‌ها حداقل فاصله را داشته باشد. در اینجا سلول ورونوی و فروشگاه بوده و از نمودار ورونوی می‌توان برای تخمین تعداد مشتریان فروشگاه استفاده نمود (در مدلسازی ما هر فروشگاه در شهر در حقیقت یک نقطه دیاگرام ورونوی می‌باشد.) تا به اینجا فرض بر این بوده که فاصله بین نقاط در شهر به صورت استاندارد اندازه گیری شده‌است که متناظر با فضای اقلیدسی است به طوریکه . به هر حال اگر ما مسئله را طوری بررسی کنیم که مشتریان تنها با وسیله نقلیه به فروشگاه رفته و مسیرهای ترافیکی به موازات محورهایX و Y باشد، مانند جزیره منهتن، بنابراین تابع فاصله واقعی فاصله خواهد بود که آن را می‌نامیم به طوری که . این تصویر نشان می‌دهد که سلول‌های ورونوی به طور قابل توجهی ازمتریک پیروی می‌کنند. ماهیت گراف دو تایی برای دیاگرام ورونوی (در مورد فضای اقلیدسی با سایت‌های نقطه‌ای) مشابه مثلث بندی دلانی برای همان مجموعه نقاط می‌باشد. بنابراین دو نقطه مجاور در پوش محدب وجود دارند اگر و تنها اگر سلول‌های ورونوی آن‌ها در یک جهت طولانی نامتناهی مشترک باشند. 144–152</ref> As همان‌طور که نشان داده شده‌است زمانی که فاصله تعیین نشده باشد لزوماً ماهیت نمودار حفظ نمی‌شود. 254–263 همان‌طور که در این جا نشان داده شده‌است در حالت عمومی ماهیت ثابت نخواهد ماند حتی اگر فضا دو بعدی (اما در شرایط محدب غیر یکنواخت و در حالت خاص غیر اقلیدسی) و سایت‌ها نقطه‌ها باشند. | ## بخش 2: نمودار ورنوی | تاریخچه و تحقیقات استفاده غیر رسمی از دیاگرام ورونوی به سال ۱۶۴۴ و توسط دکارت بر می‌گردد.یوهان پتر گوستاف لوژون دیریکله از نمودارهای ورونوی دو و سه بعدی در مطالعات فرم و حالت درجه دو در سال ۱۸۵۰ استفاده کرد. فیزیکدان انگلیسی به نام جان اسنو در سال ۱۸۵۴ از یک نمودار ورونوی استفاده کرد تا بتواند پاسخ مناسبی برای این سؤال پیدا کند که چگونه اکثریت مردم ساکن سوهو که در اثر ابتلا به بیماری وبا جان خود را از دست می‌دهند در نزدیکی پمپ‌های «خیابان ِ برود» زندگی می‌کنند که آلوده به عامل عفونت وبا می‌باشد در صورتی که اقلیت مبتلایان از سایر پمپ‌های آب استفاده می‌نمودند. دیاگرام ورونوی مورد استفاده در ژئوفیزیک و هواشناسی به منظور آنالیز داده‌های توزیع فضایی (مانند اندازه‌گیری میزان بارش)، بعد از هواشناس آمریکایی Alfredh. برای شبکه‌های عمومی در گروه لی این سلول‌ها به صورت ساده با عنوان دامنه اساسی نامیده می‌شوند. سایر نام‌های معادل برای این مفهوم (و یا موارد مهم خاص آن) عبارتند از: چندوجهی ورونوی، چند ضلعی ورونوی، دامنه (های) نفوذ، تجزیه ورونوی، موزاییک کاری (های) ورونوی، موزاییک کاری‌های دیریکله. در حالت کلی سطح مقطع سه بعدی موزاییک کاری ورونوی نمی‌تواند خودش یک دیاگرام ورونوی دو بعدی باشد. (سلول‌ها همگی چند وجهی محدب هستند.) موزاییک کاری شبکه‌های منظم در دو یا سه بعد در بسیاری از موزاییک کاری‌های معروف توسعه یافته‌است. یک شبکه دو بعدی یک موزاییک کاری شش گوش نامرتب با چند ضلعی‌های برابر و تقارن نقاط ایجاد می‌کند. توجه داشته باشید که شبکه‌های مستطیلی و مربعی می‌تواند توسط سایر شبکه‌ها نیز ایجاد شوند.(به عنوان مثال شبکه تولید شده به وسیله بردارهای (۱٬۰) و (۱/۲٬۱/۲) شبکه مربعی ایجاد می‌کند.) یک شبکه مکعبی ساده یک شش گوش مربعی می‌دهد. طرح‌های موازی با شبکه‌های مثلثی مرتب که مرکزهایشان پشت سر هم قرار گرفته‌اند منشور شش وجهی ایجاد می‌کند. برای مجموعه‌ای از نقاط (x, y) با در نظر گرفتن x در مجموعه جدا X و y در مجموعه مجزا Y به کاشی مستطیلی شکل خواهیم رسید که لزوماً نقاط در مرکز آن‌ها قرار ندارند. دیاگرام ورونوی مرتبه بالاتر اگرچه یک سلول ورونوی نرمال به عنوان یک مجموعه از نقاط با نزدیکترین فاصله به یک نقطه تنها در S تعریف شده‌اند، یک سلول ورونوی از مرتبه به عنوان یک مجموعه از نقاط نامیده می‌شود که یک مجموعه خاص از در دارند که این نزدیکترین همسایه به نقطه تنهای مورد نظر می‌باشد. به منظور تولید نمودار ورونوی از مرتبه از مجموعه Sبا دیاگرام مرتبه ام شروع نموده و هر سلول تولید شده با را با نمودار تولید شده روی مجموعه جایگزین می‌کنیم. نمودار ورونوی دورترین نقطه برای یک مجموعه نقطه‌ای، نمودار ورونوی مرتبه ام دیاگرام ورونوی با نام دیاگرام ورونوی دورترین نقطه شناخته می‌شود. برای یک مجموعه از نقاط دیاگرام ورونوی دورترین نقطه طرح را به سلول‌هایی تقسیم می‌کند که نقطه یکسان P دورترین نقطه می‌باشد. توجه داشته باشید که نقطه P دارای سلولی در دیاگرام دورترین نقطه است اگر و تنها اگر به عنوان یک راس از پوشش محدب P باشد. بنابراین را به عنوان پوشش محدب P قرار داده به طوری که هر نقطه درون با این ویژگی که نقطه q در درون سلول مربوط به سایت قرار گرفته‌است، دیاگرام ورونوی نقطه دور را به عنوان بخشی از طرح در سلول‌های تعریف می‌کنیم اگر و تنها اگر فاصلهٔ بیشتر از فاصله باشد و و و فاصله فاصله اقلیدسی بین نقطه و است. عمومیت‌ها و تغییرات به منظور روشن شدن موضوع توسط تعریف کردن، سلول‌های ورونوی می‌تواند برای متریک‌های غیر از فاصله‌های اقلیدسی (مانند ماهالانوبیس و منهتن. به هر حال در این موارد مرزهای سلول ورونوی می‌تواند نسبت به موارد اقلیدسی پیچیده تر شود. چرا که مکان هندسی هم فاصله برای دو نقطه می‌تواند به زیر فضای هم بعد یک یا دو بعدی تقسیم شود. یک نمودار ورونوی سنگین تابعی از زوج نقاط است که به منظور تعریف سلول ورونوی، تابع فاصله به وسیله ضرب یا جمع وزن‌های نقاط تولید شده اصلاح می‌شود. | ## بخش 3: نمودار ورنوی | یک دیاگرام توان نوعی لز دیاگرام ورونوی است که مجموعه‌ای از دایره‌ها توسط فاصله توانی تعریف می‌شوند. این دیاگرام همچنین می‌تواند به عنوان دیاگرام ورونوی سنگین معرفی شود به طوری که یک وزن، از مجموع شعاع هر دایره و توان دوم فاصله از مرکز دایره تعریف می‌شود.. یک پیشنهاد دیگر استفاده از دیاگرام ورونوی تقریبی است به طوری که اگر سلول‌های ورونوی دارای مرزهای فازی باشند می‌توان از این تقریب استفاده نمود..S. پیشنهاد دیگر مربوط به زمانی است که هر سایت یک دایره فازی باشد و در نتیجه سلول‌ها نیز فازی شوند. سلول‌های ورونوی همچنین با سایر ساختارهای هندسی دیگر مانند محورهای میانی (به طوری که در قطعه بندی تصویر شناسایی ماهیت نوری و سایر کاربردهای محاسباتی دیگر مورد استفاده قرار می‌گیرد.)طرح ریزی مستقیم و نمودارهای نقطه‌ای مرتبط است. وی ارتباط بین نواحی روی نقشه لندن را که از پمپ‌های آبی خاص استفاده می‌نمودند و نواحی با بیش‌ترین آمار مرگ و میر به دلیل شیوع بیماری وبا را با این دیاگرام نشان داد. یک ساختمان داده موقعیت نقطه می‌تواند در مورد دیاگرام ورونوی به منظور پاسخگویی یه جستجوی نزدیک‌ترین همسایه ایجاد شود، در جایی که شخص بخواهد نزدیکترین شی را به نقطه مورد جستجو پیدا کند. جستجوی نزدیکترین همسایه چندین کاربرد دارد:به عنوان مثال ممکن است بخواهیم نزدیکترین بیمارستان یا اشیا مشابه را در پایگاه داده پیدا کنیم. در هندسه دیاگرام‌های ورونوی می‌تواند به منظور یافتن بزرگترین محدوده خالی از مجموعه نقاط و همچنین در چند ضلعی محصور مورد استفاده قرار گیرد. به عنوان مثال برای تأسیس یک سوپر مارکت جدید در حداکثر فاصله از سایر سوپرمارکت‌های موجود که در یک شهر خاص قرار گرفته‌اند این دیاگرام کاربرد دارد. دیاگرام ورونوی و دیاگرام و دیاگرام ورونوی دورترین نقطه برای الگوریتم‌های کارا به منظور محاسبه منحنی مجموعه نقاط مورد استفاده قرار می‌گیرد. روش ورونوی کاربرد مؤثری در سنجش مدور بودن/گرد بودن در زمان ارزیابی مجموعه داده‌ها توسط دستگاه سنجش مختصات دارد. در فیزیک پلیمر دیاگرام ورونوی می‌تواند در نمایش دادن حجم خالی پلیمرها مورد استفاده قرار گیرد. در علم آب و هوا‌شناسی (اقلیم شناسی)دیاگرام‌های ورونوی در محاسبه میزان بارش یک منطقه بر مبنای اندازه‌گیری مجموعه‌ای از نقاط کاربرد دارد. در علم بوم شناسی دیاگرام ورونوی به منظور مطالعه الگوهای رشد جنگل‌ها، تاج‌پوش جنگل و همچنین استفاده مؤثر در توسعه مدل‌های پیش گویانه آتش سوزی جنگل‌ها کاربرد دارد. در گرافیک کامپیوتر دیاگرام‌های ورونوی به منظور ایجاد متن‌های اثلی و ساختمانی به کار برده می‌شوند. در هدایت ربات‌های مستقل دیاگرام‌های ورونوی به منظور یافتن مسیرهای واضح کاربرد دارند. در شیمی محاسباتی سلول‌های ورونوی که توسط موقعیت هسته در مولکول تعریف می‌شوند در محاسبه بارهای اتمی مورد استفاده قرار می‌گیرند. در دانش مواد ساختارهای میکروپلی کریستالی در آلیاژهای فلزی توسط موزاییک کاری ورونوی نمایش داده می‌شود. | ## جمع‌بندی | در اینجا حفره‌ها و سوراخ خای اکتشافی با عنوان مجموعه نقاط چندضلعی ورونوی می‌باشد.