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

نزدیک‌ترین زوج نقطه با رنگ قرمز نشان داده شده است.

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

الگوریتم ساده، پیدا کردن فاصلۀ همۀ زوج نقاط و انتخاب کمینۀ آن‌هاست که نیازمند زمانی از مرتبۀ O(n²) است. به نظر می‌رسد مسئله در زمان O(n log n) درفضای اقلیدسی یا Lp space با بعد ثابت d قابل حل باشد. در [�] [�] الگوریتم با زمان O(n log n) بهینه است.این بهینه بودن از این که [�] ( با حد پائینO(n log n) برای پیچیدگی زمانی) قابل کاهش به مسئلۀ نزدیکرین زوج است پیروی می‌کند: بررسی این‌که کمینۀ فاصله صفر است یا خیر، پس از حل مسئله نزدیکترین زوج آیا دو نقطه منطبق بر هم وجود دارند یا خیر.

در مدل محاسباتی‌ای که در نظر می‌گیریم که [�] که در زمان ثابت قابل محاسبه است باعث حل مسئله در زمان O(n log n) می‌شود. اگر در تابع سقف از حالت تصادفی استفاده کنیم مسئله در زمان خطی قابل حل است.

جستجوی جامع

نزدیکترین زوج از نقاط با استتفاده از جستجوی جامع در نظریه پیچیدگی محاسباتی O(n²) قابل محاسبه است. برای این کار باید فاصلۀ میان تمام n(n − 1) / 2 زوج نقطه را محاسبه کرده و زوجی را که کم‌ترین فاصله را دارند،برگزینیم. شبه کد این الگوریتم در زیرمشاهده می‌شود.

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

حالت صفحه

مسئله با استفاده از الگوریتم تقسیم و حل در زمانO(n log n) قابل حل است. رویه در زیر قابل مشاهده است.

1. نقاط را براساس مولفۀ xشان مرتب می‌کنیم.
2. مجموعۀ نقاط را با استفاده از یک خط عمودی به صورت {{math|x=x_mid} به دو زیرمجموعۀ با اندازۀ مساوی تقسیم می‌کنیم.
3. مسئله را به صورت بازگشتی برای زیرمجموعه‌های راست و چپ حل می‌کنیم که کمینۀ فاصله برای سمت راست و چپ به ترتیب به صورت d_Rmin و d_Lmin به دست می‌آید.
4. کمینه فاصله بین نقاطی را که یکی‌شان درزیرمجموعۀ سمت چپ قرار دارد و دیگری در زیرمجموعۀ سمت راست انتخاب می‌کنیم و آن را d_»LRmin می‌نامیم.
5. جواب نهایی کمینه فاصله میان d_LRmin d_Lmin d_Rmin است.

به نظر می‌رسد مرحلۀ 4 در زمان خطی انجام پذیرد. بار دیگر روش ساده برای این کار نیاز به محاسبۀ فاصلۀ همۀ زوج نقاط در چپ و راست است که نیازمند زمان از مرتبۀ O(n²) است.نکتۀ اصلی در خاصیت پراکندگی مجموعۀ نقاط است. می‌دانیم که نزدیک‌ترین زوج نقاط قطعاً فاصله‌ای بیش‌تر از dist= min(d_Lmin, d_Rmin) ندارد. پس کافی‌ست برای هر نقطه در سمت چپ خط جدا کننده،کافی است نقاطی را که در مستطیلی به ابعاد(dist, 2 ⋅ dist) در سمت راست خط جدا کننده قرار دارند را بررسی کنیم که در شکل نیز نمایش داده‌شده است.به علاوه این مستطیل حداکثر 6 نقطه می‌تواند در خود جای دهد که حداکثر فاصله‌شان d_Rmin است.بنابراین تعداد بهینۀ محاسبات در مرحلۀ 4،حداکثر محاسبه‌ی6n بین زوج نقاطی که یکی‌شان در سمت چپ و دیگری در سمت راست خط جدا کننده است. رابطۀ بازگشتی برقرار بین مراحل بالا T(n)T(n) = 2 T(n/2) + O(n) است که با استفاده از قضیه اصلی واکاوی الگوریتم‌ها داریم:T(n) =O(n log n).

تقسیم وحل: مستطیل جدا کننده

همانند مسئله نزدیکترین زوج نقاط ، یالی را در مثلث‌بندی دیلانی تعریف می‌کنیم که برابر دو خانۀ مجاور در دیاگرام ورونوی است. نزدیک‌ترین زوج نقاط را با استفاده از دوساختار بالا می‌توان در زمان خطی محاسبه کرد. هزینه ایجاد دو ساختارمثلث‌بندی دیلانی یا دیاگرام ورونوی از لحاظ محاسباتیO(n log n) است. در حالی که ره‌یافت تقسیم و حل برای تمام ابعاد هزینۀ محاسباتی ثابتی برابر O(n log n) دارد، این روش‌ها برای بعدهای بیش از 2 این روش‌ها مناسب نیستند.

جستارهای وابسته

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

منابع

• Thomas H. Cormen, Charles E. Leiserson, رونالد ریوست, and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 957–961 of section 33.4: Finding the closest pair of points.
• Jon Kleinberg; Éva Tardos (2006). Algorithm Design. Addison Wesley. 
• UCSB Lecture Notes
• rosettacode.org - Closest pair of points implemented in multiple programming languages
• Line sweep algorithm for the closest pair problem