تعیین نزدیکترین زوج نقاط در فضای دو بعدی

تعیین نزدیکترین زوج نقاط در فضای دو بعدی

الگوریتم:

الف)در ابتدا نودها را در این فضا براساس مختصه X شان مرتب می کنیم.

ب) سپس با در نظر گرفتن یک خط فرضی مجموعه نقاط را به دو بخش چپ و راست که هر کدام دارای n/2 عنصر هستند تقسیم می کنیم.

ج) دو زیر مسئله چپ و راست را حل کرده تا کمترین فاصله در هر دو زیر مسئله تولید شود و پاسخ هر دو زیر مسئله را S1 و S2 می نامیم.

د)S= min (S1,S2)

ه) حال اگر شبیه روش یک بعدی فاصله نزدیکترین نقطه از نقاط چپ و راست خط را نیز در محاسبات دخیل کنیم ممکن است به جواب صحیح نرسیم. لذا در این مسئله با اضافه کردن یکسری شرایط سعی می کنیم تعداد مقایسه ها را کم کنیم. می توان به اندازه S از خط وسط از هر دو طرف یک محدوده در نظر گرفت و نقاط داخل این باریکه را باهم مقایسه کرد که در نتیجه باز در بدترین شرایط تمام n/2 نقطه سمت چپ و n/2 نقطه سمت راست خط وسط در این باریکه ها قرار دارند و لذا مرتبه زمانی 〖O(n〗^2) خواهد شد ولی می توان برای هر نقطه در باریکه سمت چپ مانند p فقط نقاط واقع در مستطیل خاصی را در نظر گرفت. این مستطیل بدین شکل ساخته می شود که باید پای عمود ازنقطه نسبت به خط وسط را پیدا کرده از آن به اندازه S به بالا، پایین و راست حرکت کرد تا یک ناحیه مستطیلی شکل به طول 2S و عرض S حاصل شود. بدیهی است که حداکثر تعداد نقاط واقع در این ناحیه مستطیلی شکل برابر 6 نقطه است و لذا برای هر نقطه در باریکه سمت چپ فقط باید فاصله آن را با 6 نقطه در باریکه سمت راست محاسبه کرد و این فواصل را نیز در محاسبه کمترین فاصله دخیل کرد.

نکته1: بدلیل اینکه پیاده سازی دایره ای با شعاع S مشکل است از یک مستطیل استفاده می کنیم.

نکته2: فاصله دو نقطه (x1,y1) و (x2,y2) در فضای دوبعدی از رابطه √(〖(x1-x2)〗^2+ 〖(y1-y2)〗^2 ) √ بدست می آید.

پس مرتبه زمانی الگوریتم بصورت زیر محاسبه می شود:

T(n) = 2T [ n/2 ] + 6 [ n/2 ] = O(n.log n)

منابع

• مقدمه ای بر طراحی و تحلیل الگوریتم ها ( علی نوراله)