Distributed Spanner Construction in Doubling Metric Spaces ∗

http://homepage.cs.uiowa.edu/~sriram/papers/DD.Spanner.pdf

دورترین همسایه، درخت پوشای ماکسیمم و مسائل مرتبط در ابعاد بالا

Agarwal, Matousek, and Suri (1991) – rounding the directions

چکیده: الگوریتم تصادفی با زمان متوسط

O(m^2/3 n^2/3 log^4/3 m + m log^2 m + n log^2 n)

برای محاسبه ی دورترین همسایه های دو-رنگی بین n نقطه قرمز و m نقطه آبی در E^3 می دهیم. الگوریتم می تواند برای محاسبه ی دورترین همسایه ها یا دورترین همسایه های خارجی n نقطه در E^3 در زمان متوسط O(n^4/3 log^4/3 n) به کار رود. با استفاده از این رویه ها به عنوان اجزای سازنده، می توانیم درخت پوشای ماکسیمم اقلیدسی یا افراز دو مجموعه ای با کمترین قطر برای n نقطه را در E^3 در زمان متوسط O(n^4/3 log^7/3 n) به دست بیاوریم. بهترین زمان قبلی O(n^3/2 log^1/2 n) بود. الگوریتم ما می تواند به ابعاد بالا تعمیم یابد.

همچنین ما الگوریتمهای تقریبی سریع و ساده برای این مسائل ارائه می دهیم. این الگوریتم های تقریبی جوابهایی می سازند که مقدار واقعی را با دقت e تقریب می زنند و در زمان O(n e^(1-k)/2 log n) یا O(n e^(k-1)/2 log^2 n) در فضای k-بعدی حل می شوند.

مقدمه:

در این مقاله مسائل را در فضای اقلیدسی E^k برای تعداد ابعاد ثابت k حل می کنیم. الگوریتم کارایی برای مسائل زیر ارائه می دهیم:

1- همه ی دورترین همسایه ها: یک مجموعه S از n نقطه در E^k داده شده است، برای هر نقطه p عضو S نقطه ی q عضو S را طوری پیدا کنید که d(p,q) >= d(p,q') باشد (به ازای هر q' عضو S)؛ به q دورترین همسایه p می گویند.

2- دورترین همسایه های دو-رنگی: مجموعه R از n نقطه قرمز و مجموعه B از m نقطه آبی در E^k داده شده اند. برای هر نقطه r عضو R، نقطه ی b عضو B را طوری پیدا کنید که d(r,b) >= d(r,b') باشد (به ازای هر b' عضو B)؛ در این صورت به b دورترین همسایه رنگی r می گویند.

3- دورترین همسایه خارجی: مجموعه S از n نقطه در E^k و افرازهای آن S1,S2,...,Sm داده شده است، برای هر p عضو S اگر p عضو Si است، نقطه ی q عضو S-Si را که d(p,q) >= d(p,q') برای همه ی q' عضو S-Si برقرار باشد؛ q را دورترین همسایه خارجی p می نامیم.

4- درخت پوشای ماکسیمم اقلیدسی (EMXST): مجموعه S از n نقطه در ٍE^k داده شده است، درخت پوشای S که یالهای آن ماکسیمم فاصله بین همه ی درخت های پوشا را دارند، که طول هر یال فاصله ی اقلیدسی بین نقاط دو سر آن است را محاسبه کنید.

5- افراز دو مجموعه ای با مینیمم قطر: مجموعه S از n نقطه در E^k داده شده است، S را به دو مجموعه افراز کنید طوری که ماکسیمم بین قطر این دو مجموعه نقطه مینیمم شود.

مساله محاسبه همسایه (دورترین، نزدیک ترین، یا میانی) یک مساله اصلی در هندسه محاسباتی است که کاربردهای زیادی دارد. اما مساله ی همه ی نزدیک ترین همسایه در E^k می تواند به صورت بهینه در O(n log n) حل شود، هیچ الگوریتمی با چنین کارایی برای دورترین همسایه به ازای k>= 3 نیست. کاربردهای زیادی به نسخه های دو-رنگی و خارجی هم نیاز دارند. برای این دو مساله هم در k>=3 جواب بهینه نداریم. برای زوج قطر مساله در O(n^ (2-2/(k/2+1+gamma)) برای n نقطه در k بعد حل شده است، اما الگوریتم داده شده قابل تعمیم به دورترین/نزدیک ترین همسایه نیست. بهترین الگوریتم فعلی برای دورترین همسایه در سه بعد در زمان O(n^3/2 log^1/2 n) کار می کند. در این مقاله یک الگوریتم بهتر ولی تصادفی برای دورترین همسایه ها و مسائل مربوط به آن برای سه بعد و ابعاد بالا می دهیم.

...

2- محاسبه دورترین همسایه

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

2-1- الگوریتم برای حالت نقاط آبی زیاد و نقاط قرمز کم

به صورت تصادفی زیرمجموعه ای m/4 عضوی از نقاط آبی انتخاب می کنیم و مجموعه نقاط قرمز را به دو مجموعه n/2 عضوی افراز می کنیم و مساله را برای این زیرمساله ها حل می کنیم. به ازای نقطه قرمز iام و دورترین همسایه آبی آن b'i تعریف می کنیم: Si را توپ به مرکز نقطه قرمز و شعاع فاصله قرمز و آبی می نامیم و S'_i را خارج این توپ تعریف می کنیم. چون b'i دورترین همسایه ri بوده است، پس B' درون همه ی توپ های به مرکز نقاط قرمز می افتد و دورترین همسایه ri در B یا b'i است یا در S'i می افتد. پس نقاط اشتراک Si ها جواب ما نیستند.

...

--------------

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