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

مسئله نزدیکترین زوج نقاط یا نزدیکترین زوج یک مسئله از هندسه محاسباتی است که در آن در فضای متری n نقطه به عنوان ورودی گرفته می‌شود و زوج نقطه‌ای که کوتاه‌ترین فاصله بین آن‌دو وجود دارد، پیدا می‌شود. مسئله نزدیکترین زوج برای نقاط در صفحهٔ اقلیدسیM. I. Shamos and D. Hoey. "Closest-point problems." In Proc. 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 151—162, 1975 (DOI 10.1109/SFCS.1975.8) از اولین مسائل هندسه بود که مطالعات سیستماتیک در نظریه پیچیدگی محاسباتی، الگوریتم‌های هندسه شد.

الگوریتم ساده، پیدا کردن فاصلهٔ همهٔ زوج نقاط و انتخاب کمینهٔ آن‌هاست که نیازمند زمانی از مرتبهٔ است. به نظر می‌رسد مسئله در زمان در فضای اقلیدسی با بعد ثابت قابل حل باشد. در درخت تصمیم جبری مدل محاسبه الگوریتم با زمان با توجه به کاهشی از مساله یکتایی عنصر بهینه است. در مدل محاسباتی چنین فرض می‌شود که تابع کف در زمان ثابت قابل محاسبه است و مساله می‌تواند در حل شود.S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979 اگر در تابع کف از حالت تصادفی استفاده کنیم مسئله در نیز قابل حل است.S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput. , 118(1):34—37,1995

 جستجوی جامع 
نزدیکترین زوج از نقاط با استتفاده از جستجوی جامع در نظریه پیچیدگی محاسباتی قابل محاسبه است. برای این کار باید فاصلهٔ میان تمام زوج نقطه را محاسبه کرده و زوجی را که کم‌ترین فاصله را دارند، انتحاب کنیم. شبه کد این الگوریتم در زیرمشاهده می‌شود.minDist = infinity
for i = 1 to length(P) - 1
 for j = i + 1 to length(P)
  let p = P[i], q = P[j]
  if dist(p, q) < minDist:
   minDist = dist(p, q)
   closestPair = (p, q)
return closestPair

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

به نظر می‌رسد مرحلهٔ ۴ در زمان خطی انجام پذیرد. بار دیگر روش ساده برای این کار نیاز به محاسبهٔ فاصلهٔ همهٔ زوج نقاط در چپ و راست است که نیازمند زمان از مرتبهٔ  است. نکتهٔ اصلی در خاصیت پراکندگی مجموعهٔ نقاط است. می‌دانیم که نزدیک‌ترین زوج نقاط قطعاً فاصله‌ای بیش‌تر از  ندارد. پس کافی‌ست برای هر نقطه در سمت چپ خط جدا کننده، کافی است نقاطی را که در مستطیلی به ابعاد در سمت راست خط جدا کننده قرار دارند را بررسی کنیم که در شکل نیز نمایش داده‌شده است. به علاوه این مستطیل حداکثر ۶ نقطه می‌تواند در خود جای دهد که حداکثر فاصله‌شان  است؛ بنابراین تعداد بهینهٔ محاسبات در مرحلهٔ ۴، حداکثر محاسبه‌ی بین زوج نقاطی که یکی‌شان در سمت چپ و دیگری در سمت راست خط جدا کننده است. رابطهٔ بازگشتی برقرار بین مراحل بالا  است که با استفاده از قضیه اصلی واکاوی الگوریتم‌ها داریم:.

راست|بندانگشتی|تقسیم وحل: مستطیل جدا کننده

همانند مسئله نزدیکترین زوج نقاط، یالی را در مثلث‌بندی دیلانی تعریف می‌کنیم که برابر دو خانهٔ مجاور در دیاگرام ورونوی است. نزدیک‌ترین زوج نقاط را با استفاده از دوساختار بالا می‌توان در زمان خطی محاسبه کرد. هزینه ایجاد دو ساختارمثلث‌بندی دیلانی یا دیاگرام ورونوی از لحاظ محاسباتی است. در حالی که ره‌یافت تقسیم و حل برای تمام ابعاد هزینهٔ محاسباتی ثابتی برابر  دارد، این روش‌ها برای بعدهای بیش از ۲ این روش‌ها مناسب نیستند.

Algorithm Closest_Pair(p1, p2, ..., pn);
Input: p1, p2, ..., pn (a set of n points in the plane)
Output: d (the distance between the two closest points in the set)

begin
    sort the points according to their x coordinates;
    {''this sorting is done only once at the beginning''}
    Didive the set into two equal-sized parts;
    Recursively do the following:
        compute the minimal distance in each part;
        sort the points in each part according to their y coordinates;
    Merge the two sorted lists into one sorted list;
    {''Notice that we must merge before we eliminate; 
        we need to supply the whole set sorted to the next level of the recursion''}
    Let d be the minimal of the minimal distances;
    Eliminate points that lie further than d apart from the seperation line;
    Scan the points in the y order and compute the distances of each point to its five neighbors;
    if any of these distances is less than d the update d;
end

 یادداشت‌ها 

 جستارهای وابسته 
 جستجوی نزدیکترین همسایه
 پوشش مجموعه

 منابع 

 Thomas H. Cormen, Charles E. Leiserson, رونالد ریوست، and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها, Second Edition. MIT Press and McGraw-Hill, 2001. . Pages 957–961 of section 33.4: Finding the closest pair of points.

UCSB Lecture Notes
rosettacode.org - Closest pair of points implemented in multiple programming languages
Line sweep algorithm for the closest pair problem

رده:الگوریتم‌های هندسی