الگوریتم فورچون کیست؟ توضیح بده.
الگوریتم فورچون یک الگوریتم خط جارویی برای ساختن نمودار ورونی از یک دسته نقطه در صفحه با استفاده از زمان formula_1 و حافظۀ formula_2 است.این الگوریتم اولین بار توسط استیون فورچون در سال ۱۹۸۶ در مقالۀ "یک الگوریتم خط جارویی برای نمودارهای ورونی" چاپ شد.توضیح الگوریتم.این الگوریتم هم از خط جارویی و هم از "خط ساحلی" استفاده می‌کند که هردوی این خطوط در حین پیشرفت الگوریتم روی صفحه حرکت می‌کنند. خط جارویی خط مستقیمی است که ما به صورت توافقی می‌توانیم فرض کنیم که یک خط عمودی است و از چپ به راست صفحه حرکت می‌کند. در هر لحظه در طی الگوریتم نقاط ورودی سمت چپ خط جارویی با نمودار ورونی یکپارچه خواهند شد درحالی که نقاط سمت راست خط هنوز در نظر گرفته نشده‌اند. خط ساحلی یک خط نیست، بلکه یک منحنی مرکب در سمت چپ خط جارویی است که از تکه‌های سهمیها تشکیل شده است؛ این خط صفحه را به گونه‌ای تقسیم می‌کند که در آن نمودار ورونی، بدون توجه به وجود نقاط ممکن در سمت راست خط جارویی، از بقیۀ صفحه قابل تشخیص است. برای هر نقطه در سمت چپ خط جارویی، میتوان یک سهمی از نقاط هم‌فاصله از آن نقطه و خط جارویی تعریف کرد. خط ساحلی مرز مجموعۀ این سهمی‌ها است. هر چه خط جارویی پیشروی می‌کند رئوس خط ساحلی، که محل تلاقی دو سهمی است، یال‌های نمودار ورونی را رسم می‌کنند. خط ساحلی طوری پیشرفت می‌کند که رأس هر سهمی دقیقأ در وسط نقاط اولیۀ خط جارویی و جایگاه جدید خط جارویی قرار بگیرد.این الگوریتم از داده ساختارها استفاده می‌کند: یک درخت جستجوی دودویی که ساختار ترکیبی خط ساحلی را توصیف می‌کند و یک صف اولویت‌دار که رخدادهای بالقوۀ بعدی را که می‌توانند ساختار خط ساحلی را تغییر دهند لیست می‌کند. این رخدادها شامل اضافه کردن یک سهمی دیگر به خط ساحلی هستند (وقتی که خط جارویی از نقطۀ ورودی دیگری عبور می‌کند) و برداشتن منحنی از خط ساحلی (وقتی که خط جارویی با یک دایرۀ عبورکننده از سه نقطه، که سهمی‌هایشان بخش‌های متوالی خط ساحلی را تشکیل می‌دهند، مماس می‌شود). هر رخداد می‌تواند توسط محور xهای خط جارویی در محل وقوع رخداد، اولویت‌بندی شود. الگوریتم از برداشتن مکرر رخداد بعدی از صف اولویت‌دار، یافتن تغییراتی که آن رخداد در خط ساحلی ایجاد می‌کند و بهنگام‌سازی داده ساختارها، تشکیل می‌شود. از آنجا که formula_2 رخداد وجود دارند تا پردازش شوند (که هرکدام با برخی ویژگی‌های دیاگرام ورونی مرتبط هستند) و زمان formula_4 برای پردازش یک رخداد (که هرکدام شامل تعداد ثابتی از اعمال درخت جستجوی دودویی و صف اولویت‌دار هستند) زمان کلی الگوریتم formula_1 است.شبه‌کد.شبه‌کد توضیحات الگوریتم. let formula_6 be the transformation formula_7, where formula_8 is the Euclidean distance between formula_9 and the nearest site let formula_10 be the "beach line" let formula_11 be the region covered by site formula_12. let formula_13 be the boundary ray between sites formula_12 and formula_15. let formula_16 be the sites with minimal formula_17-coordinate, ordered by formula_18-coordinate formula_19 create initial vertical boundary rays formula_20 formula_21 while not IsEmpty(formula_22) do formula_12 ← DeleteMin(formula_22) case formula_12 of formula_12 is a site in formula_27: find the occurrence of a region formula_28 in formula_10 containing formula_12, bracketed by formula_31 on the left and formula_32 on the right create new boundary rays formula_33 and formula_34 with bases formula_12 replace formula_28 with formula_37 in formula_10 delete from formula_22 any intersection between formula_31 and formula_32 insert into formula_22 any intersection between formula_31 and formula_33 insert into formula_22 any intersection between formula_34 and formula_32 formula_12 is a Voronoi vertex in formula_27: let formula_12 be the intersection of formula_51 on the left and formula_52 on the right let formula_53 be the left neighbor of formula_51 and let formula_55 be the right neighbor of formula_52 in formula_10 create a new boundary ray formula_58 if formula_59, or create formula_60 if formula_12 is right of the higher of formula_15 and formula_63, otherwise create formula_64 replace formula_65 with newly created formula_32 in formula_10 delete from formula_22 any intersection between formula_53 and formula_51 delete from formula_22 any intersection between formula_52 and formula_55 insert into formula_22 any intersection between formula_53 and formula_32 insert into formula_22 any intersection between formula_32 and formula_55 record formula_12 as the summit of formula_51 and formula_52 and the base of formula_32 output the boundary segments formula_51 and formula_52 endcase endwhile output the remaining boundary rays in formula_10بخش‌ها و دیسک‌های وزن‌دار.همان‌طور که فورچون در توضیح داده است، یک نوع الگوریتم توسعه‌یافتۀ خط جارویی می‌تواند برای ساخت نمودار ورونی وزن‌دارافزایشی استفاده شود، که در آن فاصلۀ هر بخش با وزن آن تعیین می‌شود؛ که این می‌تواند برابر با نمودار ورونی مجموعه‌ای از دیسک‌های هم‌مرکز بخش‌ها و به شعاع وزن آن‌ها باشد.زمانی که از نمودار ورونی برای ساخت treemapها استفاده می‌شود، می‌توان از بخش‌های وزن‌دار برای کنترل مکان‌های سلولی ورونی استفاده کرد. در یک دیاگرام ورونی وزن‌دار افزایشی، نیم‌ساز بین بخش‌ها به‌طور عمومی یک هذلولی است در حالی که در نمودارهای ورونی غیروزن‌دار و نمودار پاور دیسک‌ها نیم‌ساز یک خط مستقیم است.