دیاگرام ورونوی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
ده فروشگاه در شهر مسطح و سلول‌های ورونوی آنها (نسخه بزرگتر پایین).

در علم ریاضیات دیاگرام ورونوی روشی برای تقسیم فضا به تعدادی ناحیه می‌باشد. در این دیاگرام به هر مجموعه‌ای از نقاط (که دامنه‌ها، سایت‌ها و یا ژنراتورها نامیده می‌شوند) ناحیه‌ای اختصاص داده می‌شود. این نواحی سلول‌های ورونوی نامیده می‌شود. برای یک مجموعه از نقاط دیاگرام ورونوی سطح را به مناطقی تقسیم بندی می‌کند که برای هر نقطه از مجموعه نقاط یک منطقه تعریف می‌شود. به طوری که تمام نقاط این منطقه به نقطه تولید کننده آن منطقه نزدیکتر می‌باشد. از کاربردهای این دیاگرام در مثلث بندی دلانی می‌باشد.

این دیاگرام بعد از Peter Gustav Lejeune Dirichlet به نام موزاییک کاری دیریکله و بعد از Georgy Voronoi به نام موزاییک کاری ورونوی یا تجزیه ورونوی نامیده شد. دیاگرام‌های ورونوی در علوم و فناوری‌های متعدد و یا حتی در هنر کاربرد دارد و تاکنون کاربردهای متفاوتی از آن در زمینه‌های خاص گزارش شده است.[۱][۲]

ساده ترین مورد[ویرایش]

در ساده ترین و بارزترین مورد (همان طور که در شکل نشان داده شده است) یک مجموعه متناهی از نقاط {p۱،...،pn} را در یک فضای اقلیدسی در این مورد هر سایت pk یک نقطه ساده بوده که برای آن سلول ورونوی Rk (که ناحیه ورونوی یا سلول دیریکله نامیده می‌شود.)درنظر می‌گیریم Rk شامل نقاط دیگری نیز می‌باشد که فاصله هر نقطه درون Rk تا pk کمتر و یا برابر با فاصله سایر سایت‌ها تا pk می‌باشد. این سلول از به اشتراک گذاشتن نیمی از فضا حاصل می‌شود و بنابراین یک چند ضلعی محدب نامیده می‌شود. بخش‌های دیاگرام ورونوی تمامی نقاط سطح می‌باشد که با دو تا از نزدیکترین سایت‌ها هم فاصله می‌باشد. رأس‌های ورونوی (گره‌ها) نقاط هم فاصله با سه (یا تعداد بیشتر) سایت‌ها می‌باشد.

تعریف رسمی[ویرایش]

فرض کنید  \displaystyle{X} یک فضا (مجموعه ناتهی) با تابع فاصله  d باشد. فرض کنید \displaystyle{K} یک مجموعه از اندیس‌ها و (P_k)_{k \in K} یک چند تایی (مرتب شده) از زیر مجموعه‌های ناتهی (سایت‌ها) در فضای \displaystyle{X} باشد. سلول ورونوی یا ناحیه ورونوی  \displaystyle{R_k} که متناظر با \displaystyle{P_k} می‌باشد. به طوریکه  \displaystyle{R_k} مجموعه‌ای از نقاط در فضای \displaystyle{X} می‌باشد که فاصله اشان تا \displaystyle{P_k} کوچکتر یا مساوی سایر نقاط \displaystyle{P_j} می‌باشد جاییکه j مخالف هر اندیس k می‌باشد. به عبارت دیگر اگر d(x,A)=\inf\{d(x,a) \,|\, a\in A\} مشخص کننده فاصله بین x و زیر مجموعه A باشد پس  R_k = \{x \in X\,\, | \,\,d(x,P_k) \leq d(x, P_j)\,\, \text{for all}\,\, j\neq k\}. .
نمودار ورونوی یک چندتایی ساده از سلول‌های (R_k)_{k \in K} می‌باشد. در اصل بعضی از سایت‌ها می‌توانند از وسط قطع شده و حتی در یک ناحیه قرار گیرند (یک کاربرد آن برای فروشگاه‌ها شرح داده شده است.)اما معمولاً فرض بر این است که در یک ناحیه به صورت مجزا قرار گیرند. به علاوه تعداد نامتناهی سایت در این دیاگرام می‌توان تعریف کرد (که کاربرد در هندسه محاسباتی و کریستالوگرافی می‌باشد.)اما غالباً تعداد متناهی سایت در نظر گرفته می‌شود. در مورد خاص فضا یک فضای اقلیدسی با بعد متناهی می‌باشد، هر سایت یک نقطه بوده که بسیاری از نقاط متناهی درنظر گرفته می‌شوند به طوری که همه آنها متفات می‌باشند. پس سلول‌های ورونوی چند وجهی‌های محدب بوده و می‌توان آنها را با روش‌های ترکیبی و با استفاده از رئوس، نمای دو بعدی و... نمایش داد. گاهی اوقات ساختار ترکیبی کاهشی به دیاگرام ورونوی ارجاع داده می‌شود. به هر حال در حالت کلی سلول‌های ورونوی محدب یا پیوسته نمی‌باشد.

توضیحات[ویرایش]

به عنوان یک توضیح ساده، مجموعه از فروشگاه‌ها را در یک شهر مسطح در نظر می‌گیریم. فرض کنید که می‌توان تعداد مشتریان فروشگاه را تخمین زد. در نظر می‌گیریم سایر پارامترها (مانند قیمت‌ها، محصئلات، کیفیت خدمات و...)ثابت باشد. به طوریکه تنها فاکتور انتخاب فروشگاه توسط مشتریان فاصله تا فروشگاه باشد. بنابراین مشتریان فروشگاهی را انتخاب می‌کنند که از موقعیت آنها حداقل فاصله را داشته باشد. در اینجا سلول ورونوی  \displaystyle{R_k} و فروشگاه\displaystyle{P_k} بوده و از نمودار ورونوی می‌توان برای تخمین تعداد مشتریان فروشگاه استفاده نمود (در مدلسازی ما هر فروشگاه در شهر در حقیقت یک نقطه دیاگرام ورونوی می‌باشد.) تا به اینجا فرض بر این بوده که فاصله بین نقاط در شهر به صورت استاندارد اندازه گیری شده است که متناظر با فضای اقلیدسی است به طوریکه  d((a_1,a_2),(b_1,b_2))=\sqrt{(a_1-b_1)^2+(a_2-b_2)^2}.
به هر حال اگر ما مسئله را طوری بررسی کنیم که مشتریان تنها با وسیله نقلیه به فروشگاه رفته و مسیرهای ترافیکی به موازات محورهایX و Y باشد، مانند جزیره منهتن، بنابراین تابع فاصله واقعی فاصله \ell_1 خواهد بود که آن را  d می‌نامیم به طوری که  \displaystyle{d((a_1,a_2),(b_1,b_2))=|a_1-b_1|+|a_2-b_2|}.

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


ماهیت[ویرایش]

  • گراف دو تایی برای دیاگرام ورونوی (در مورد فضای اقلیدسی با سایت‌های نقطه‌ای) مشابه مثلث بندی دلانی برای همان مجموعه نقاط می‌باشد.
  • نزدیکترین جفت نقاط متعلق به دو سلول مجاور در دیاگرام ورونوی می‌باشد.
  • فرض کنید که مجموعه‌ای از نقاط در فضای اقلیدسی داده شده باشد. بنابراین دو نقطه مجاور در پوشش محدب وجود دارند اگر و تنها اگر سلول‌های ورونوی آن‌ها در یک جهت طولانی نامتناهی مشترک باشند.
  • اگر فضای مورد مطالعه یک فضای هنجار و فاصله هر سایت قابل دسترسی باشد (به عنوان مثال هنگامی که یک سایت یک مجموعه فشرده یا توپ محصور شده باشد) پس هر سلول ورونوی می‌تواند به عنوان اجتماعی از قطعات خطی ناشی از سایت‌ها نمایش داده شود.[۳] Asهمان طور که نشان داده شده است زمانی که فاصله تعیین نشده باشد لزوماً ماهیت نمودار حفظ نمی‌شود.
  • تحت شرایط عمومی نسبی (فضای مورد مطالعه فضایی واحد و محدب و به احتمال زیاد دارای بعد نامحدود بوده و در نتیجه تعداد بسیار نامحدودی سایت در حالت عمومی وجود دارد.)سلول‌های ورونوی دارای ماهیت پایدار معین خواهند بود: تغییر کوچکی در شکل سایت‌ها، به عنوان مثال ایجاد تغییر توسط انتقال و یا تحریف، منجر به تغییر شکل سلول‌های ورونوی می‌شود که این عمر به دلیل پایدار هندسی دیاگرام ورونوی می‌باشد..[۴]همان طور که در این جا نشان داده شده است در حالت عمومی ماهیت ثابت نخواهد ماند حتی اگر فضا دو بعدی (اما در شرایط محدب غیر بکنواخت و در حالت خاص غیر اقلیدسی) و سایت‌ها نقطه‌ها باشند.

تاریخچه و تحقیقات[ویرایش]

استفاده غیر رسمی از دیاگرام ورونوی به سال ۱۶۴۴ و توسط دکارت بر می‌گردد.Peter Gustav Lejeune Dirichlet از نمودارهای ورونوی دو و سه بعدی در مطالعات فرم و حالت درجه دو در سال ۱۸۵۰ استفاده کرد. فیزیدان انگلیسی به نام John Snow در سال ۱۸۵۴ از یک نمودار ورونوی استفاده کرد تا بتواند پاسخ مناسبی برای این سوال پیدا کند که چگونه اکثریت مردم ساکن سوهو که در اثر ابتلا به بیماری وبا جان خود را از دست می‌دهند در نزدیکی پمپ‌های Broad Street زندگی می‌کنند که آلوده به عامل عفونت وبا می‌باشد در صورتی که اقلیت مبتلایان از سایر پمپ‌های آب استفاده می‌نمودند.

دیاگرام ورونوی بعد از ریاضیدان اوکراینی Georgy Fedosievych Voronyi با این نام شناخته شد. ورونوی در سال ۱۹۰۸ مطالعات خود را بر این دیاگرام در فضای n بعدی عمومی انجام داد. دیاگرام ورونوی مورد استفاده در ژئوفیزیک و هواشناسی به منظور آنالیز داده‌های توزیع فضایی (مانند اندازه گیری میزان بارش)، بعد از هواشناس آمریکایی Alfredh. Thiessen با نام چند ضلعی Thiessen شناخته شد. در فیزیک مواد متراکم و فشرده مانند موزاییک کاری‌ها به عنوان سلول واحد Wigner-Seitz شناخته می‌شود.موزاییک کاری ورونوی در تکانه شبکه دو طرفه با نام مناطق Brillouin شناخته می‌شود. برای شبکه‌های عمومی در Lie groups این سلول‌ها به صورت ساده با عنوان دامنه اساسی نامیده می‌شوند. در زمینه فضاهای متریک عمومی سلول‌ها غالباً چندضلعی اساسی متریک نامیده می‌شود. سایر نام‌های معادل برای این مفهموم (و یا موارد مهم خاص آن) عبارتند از: چندوجهی ورونوی، چند ضلعی ورونوی، دامنه (های) نفوذ، تجزیه ورونوی، موزاییک کاری (های) ورونوی، موزاییک کاری‌های دیریکله.

نمونه‌ها[ویرایش]

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

موزاییک کاری شبکه‌های منظم در دو یا سه بعد در بسیاری از موزاییک کاری‌های معروف توسعه یافته است.

  • یک شبکه دو بعدی یک موزاییک کاری شش گوش نامرتب با چند ضلعی‌های برابر و تقارن نقاط ایجاد می‌کند. در مورد شبکه مثلثی منظم موزاییک کاری منظم خواهیم داشت. در مورد شبکه مستطیلی، شش ضلعی به مستطیل در سطر و ستون کاهش پیدا می‌کند. یک شبکه مربعی یک موزاییک کاری منظم از مربعات را ایجاد می‌کند. توجه داشته باشید که شبکه‌های مستطیلی و مربعی می‌تواند توسط سایر شبکه‌ها نیز ایجاد شوند.(به عنوان مثال شبکه تولید شده به وسیله بردارهای (۱٬۰) و (۱/۲٬۱/۲) شبکه مربعی ایجاد می‌کند.)
  • یک شبکه مکعبی ساده یک شش گوش مربعی می‌دهد.
  • یک شبکه شش ضلعی فشرده فضای موزاییک کاری دوازده سطحی لوزی-ذوزنقه می‌دهد.
  • یک شبکه مرکز وجوه پر فضای موزاییک کاری دوازده سطحی لوزی شکل تولید می‌کند.
  • یک شبکه مرکز پر یک فضای موزاییک کاری هشت وجهی کوتاه می‌دهد.
  • طرح‌های موازی با شبکه‌های مثلثی مرتب که مرکزهایشان پشت سر هم قرار گرفته‌اند منشور شش وجهی ایجاد می‌کند.
  • شبکه‌های شش وجهی مرکز پر یک فضای موزاییک کاری دوازده سطحی شش وجهی –لوزی می‌دهد.

برای مجموعه‌ای از نقاط (xy) با درنظر گرفتن x در مجموعه جدا X و y در مجموعه مجزا Y به کاشی مستطیلی شکل خواهیم رسید که لزوماً نقاط در مرکز آنها قرار ندارند.

دیاگرام ورونوی مرتبه بالاتر[ویرایش]

اگرچه یک سلول ورونوی نرمال به عنوان یک مجموعه از نقاط با نزدیکترین فاصله به یک نقطه تنها در S تعریف شده‌اند، یک سلول ورونوی از مرتبه n به عنوان یک مجموعه از نقاط نامیده می‌شود که یک مجموعه خاص از n در S دارند که این n نزدیکترین همسایه به نقطه تنهای مورد نظر می‌باشد. دیاگرام ورونی از مرتبه بالاتر هم چنین فضا را طبقه بندی می‌کنند.

دیاگرام ورونوی مرتبه بالاتر می‌توانند به صورت بازگشتی تولید شوند. به منظور تولید نمودار ورونوی از مرتبه n از مجموعه Sبا دیاگرام مرتبه (1−n)ام شروع نموده و هر سلول تولید شده با{X = {x۱x۲, ... , xn−1 را با نمودار تولید شده روی مجموعه  S − X جایگزین می‌کنیم.

نمودار ورونوی دورترین نقطه[ویرایش]

برای یک مجموعه n نقطه‌ای، نمودار ورونوی مرتبه (n − 1) ام دیاگرام ورونوی با نام دیاگرام ورونوی دورترین نقطه شناخته می‌شود.

برای یک مجموعه از نقاط {S = {p۱p۲, ... , pn دیاگرام ورونوی دورترین نقطه طرح را به سلول‌هایی تقسیم می‌کند که نقطه یکسان P دورترین نقطه می‌باشد. توجه داشته باشید که نقطه P دارای سلولی در دیاگرام دورترین نقطه است اگر و تنها اگر به عنوان یک راس از پوشش محدب P باشد. بنابراین {H = {h۱h۲, ... , hk را به عنوان پوشش محدب P قرار داده به طوری که هر نقطه درون H با این ویژکی که نقطه q در درون سلول مربوط به سایت hi قرار گرفته است، دیاگرام ورونوی نقطه دور را به عنوان بخشی از طرح در سلول‌های k تعریف می‌کنیم اگر و تنها اگر فاصلهٔ (q, hi) بیشتر از فاصله (q, pj) باشد و pj ∈ S و hipj و فاصله (q,p) فاصله اقلیدسی بین نقطه p و q است.[۵][۶]

عمومیت‌ها و تغییرات[ویرایش]

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

یک نمودار ورونوی سنگین تابعی از زوج نقاط است که به منظور تعریف سلول ورونوی، تابع فاصله به وسیله ضرب و یا جمع وزن‌های نقاط تولید شده اصلاح می‌شود. در مقابل سلول‌های ورونوی توسط فاصله‌های متریک تعریف می‌شود. در این مورد برخی از سلول‌های ورونوی ممکن است خالی باشند. یک دیاگرام توان نوعی لز دیاگرام ورونوی است که مجموعه‌ای از دایره‌ها توسط فاصله توانی تعریف می‌شوند. این دیاگرام همچنین می‌تواند به عنوان دیاگرام ورونوی سنگین معرفی شود به طوری که یک وزن، از مجموع شعاع هر دایره و توان دوم فاصله از مرکز دایره تعریف می‌شود.[۷]

دیاگرام ورونوی n نقطه در فضای d بعدی، نیازمند فضای ذخبره سازی O(n^{\lceil d/2 \rceil}) می‌باشد. بنابراین دیاگرام ورونوی اغلب برای d > 2 امکان پذیر نمی‌باشد. یک پیشنهاد دیگر استفاده از دیاگرام ورونوی تقریبی است به طوری که اگر سلول‌های ورونوی دارای مرزهای فازی باشند می‌توان از این تقریب استفاده نمود..[۸]پیشنهاد دیگر مربوط به زمانی است که هر سایت یک دایره فازی باشد و در نتیجه سلول‌ها نیز فازی شوند.[۹]

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

کاربردها[ویرایش]

  • در علم بیماری‌های واگیردار دیاگرام ورونوی می‌تواند در منابع وابسته به عفونت در بیماری‌های مسری مورد استفاده قرار گیرد. یکی از موارد استفاده اولیه دیاگرام‌های ورونوی توسط John Snow در سال ۱۸۵۴ در زمان شیوع وبا در سوهو و در Broad Street می‌باشد. وی ارتباط بین نواحی روی نقشه لندن را که از پمپ‌های آبی خاص استفاده می‌نمودند و نواحی با بیش ترین آمار مرگ و میر به دلیل شیوع بیماری وبا را با این دیاگرام نشان داد.
  • یک ساختمان داده موقعیت نقطه می‌تواند در مورد دیاگرام ورونوی به منظور پاسخگویی یه جستجوی نزدیک ترین همسایه ایجاد شود، در جایی که شخص بخواهد نزدیکترین شی را به نقطه مورد جستجو پیدا کند. جستجوی نزدیکترین همسایه چندین کاربرد دارد:به عنوان مثال ممکن است بخواهیم نزدیکترین بیمارستان و یا اشیا مشابه را در پایگاه داده پیدا کنیم. بیش ترین کاربرد در رقمی سازی بردار و معمولاً در فشرده سازی داده‌ها می‌باشد.
  • در هندسه دیاگرام‌های ورونوی می‌تواند به منظور یافتن بزرگترین محدوده خالی از مجموعه نقاط و همچنین در چند ضلعی محصور مورد استفاده قرار گیرد. به عنوان مثال برای تاسیس یک سوپر مارکت جدید در حداکثر فاصله از سایر سوپرمارکت‌های موجود که در یک شهر خاص قرار گرفته‌اند این دیاگرام کاربرد دارد.
  • دیاگرام ورونوی و دیاگرام و دیاگرام ورونوی دورترین نقطه برای الگوریتم‌های کارا به منظور محاسبه منحنی مجموعه نقاط مورد استفاده قرار می‌گیرد.
  • روش ورونوی کاربرد موثری در سنجش مدور بودن/گرد بودن در زمان ارزیابی مجموعه داده‌ها توسط دستگاه سنجش مختثات دارد.

در فیزیک پلیمر دیاگرام ورونوی می‌تواند در نمایش دادن حجم خالی پلیمرها مورد استفاده قرار گیرد.

  • در شبکه دیاگرام‌های ورونوی می‌تواند در استخراج ضرفیت شبکه بی سیم استفاده شود.
  • در علم آب و هوا شناسی (اقلیم شناسی)دیاگرام‌های ورونوی در محاسبه میزان بارش یک منطقه بر مبنای اندازه گیری مجموعه‌ای از نقاط کاربرد دارد. در زمینه این کاربرد غالباً به چندضلعی Thiessen ارجاع داده می‌شود.
  • در علم بوم شناسی دیاگرام ورونوی به منظور مطالعه الگوهای رشد جنگل‌ها، تاج‌پوش جنگل و همچنین استفاده موثر در توسعه مدل‌های پیش گویانه آتش سوزی جنگل‌ها کاربرد دارد.
  • در گرافیک کامپیوتر دیاگرام‌های ورونوی به منظور ایجاد متن‌های اثلی و ساختمانی به کار برده می‌شوند.
  • در هدایت ربات‌های مستقل دیاگرام‌های ورونوی به منظور یافتن مسیرهای واضح کاربرد دارند.
  • در شیمی محاسباتی سلول‌های ورونوی که توسط موقعیت هسته در مولکول تعریف می‌شوند در محاسبه بارهای اتمی مورد استفاده قرار می‌گیرند. این امر توسط روش چگالی تغییر شکل ورونوی انجام می‌پذیرد.
  • در دانش مواد ساختارهای میکروپلی کریستالی در آلیاژهای فلزی توسط موزاییک کاری ورونوی نمایش داده می‌شود.
  • در استخراج معدن چند ضلعی ورونوی به منظور تخمین ذخایر مواد با ارزش، مواد معدنی و یا سایر منابع کاربرد دارد. در اینجا حفره‌ها و سوراخ خای اکتشافی با عنوان مجموعه نقاط چندضلعی ورونوی می‌باشد.
  • دریادگیری ماشینی دیاگرام‌های ورونوی در انجام طبقه بندی 1-NN کاربرد دارد.[۱۰]

جستارهای وابسته[ویرایش]

الگوریتم‌ها

  • الگوریتم Bowyer-Watson الگوریتمی برای ایجاد دیاگرام ورونوی برای هر بعدی می‌باشد.
  • الگوریتم Fortune's بک الگوریتم ((O(n log (n به منظور ایجاد دیاگرام ورونوی از مجموعه نقاط در طرح می‌باشد.
  • الگوریتم Lloyd's یک موزاییک کاری ورونوی در فضای با بعد دلخواه تولید می‌کند.

موضوعات مرتبط

یادداشت‌ها[ویرایش]

  1. Franz Aurenhammer (1991). Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345–405, 1991
  2. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations – Concepts and Applications of Voronoi Diagrams. 2nd edition. John Wiley, 2000, 671 pages ISBN 0-471-98635-6
  3. Daniel Reem, An algorithm for computing Voronoi diagrams of general generators in general normed spaces, In Proceedings of the sixth International Symposium on Voronoi Diagrams in science and engineering (ISVD 2009), 2009, pp. 144–152
  4. Daniel Reem, The geometric stability of Voronoi diagrams with respect to small changes of the sites, Full version: arXiv 1103.4125 (2011), Extended abstract in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG 2011), pp. 254–263
  5. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2008). Computational Geometry (Third edition ed.). Springer-Verlag.  7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
  6. Skyum, Sven (1991). "A simple algorithm for computing the smallest enclosing circle". Information Processing Letters 37(1991)121–125. , contains a simple algorithm to compute the farthest-point Voronoi diagram.
  7. Edelsbrunner, Herbert (۱۹۸۷), "13.6 Power Diagrams", Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science ۱۰, Springer-Verlag, pp. ۳۲۷–۳۲۸  .
  8. S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721–730.
  9. Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). "Uncertain Voronoi Diagram". Information Processing Letters (Elsevier) 109 (13): 709–712. DOI:10.1016/j.ipl.2009.03.007. 
  10. Tom M. Mitchell (1997). Machine Learning (International Edition 1997 ed.). McGraw-Hill. p. 233. ISBN 0-07-042807-7. 

منابع[ویرایش]

پیوند به بیرون[ویرایش]

جستجو در ویکی‌انبار در ویکی‌انبار پرونده‌هایی دربارهٔ دیاگرام ورونوی موجود است.