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

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

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

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

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

جستجوی جامع[ویرایش]

نزدیکترین زوج از نقاط با استتفاده از جستجوی جامع در نظریه پیچیدگی محاسباتی O(n2) قابل محاسبه است. برای این کار باید فاصله‌ی میان تمام 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=xmid} به دو زیرمجموعه‌ی با اندازه‌ی مساوی تقسیم می‌کنیم.
  3. مساله را به صورت بازگشتی برای زیرمجموعه‌های راست و چپ حل می‌کنیم که کمینه‌ی فاصله برای سمت راست و چپ به ترتیب به صورت dRmin و dLmin به دست می‌آید.
  4. کمینه فاصله بین نقاطی را که یکی‌شان درزیرمجموعه‌ی سمت چپ قرار دارد و دیگری در زیرمجموعه‌ی سمت راست انتخاب می‌کنیم و آن را d»LRmin می‌نامیم.
  5. جواب نهایی کمینه فاصله میان dLRmin dLmin dRmin است.

به نظر می‌رسد مرحله‌ی 4 در زمان خطی انجام پذیرد. بار دیگر روش ساده برای این کار نیاز به محاسبه‌ی فاصله‌ی همه‌ی زوج نقاط در چپ و راست است که نیازمند زمان از مرتبه‌ی O(n2) است.نکته‌ی اصلی در خاصیت پراکندگی مجموعه‌ی نقاط است. می‌دانیم که نزدیک‌ترین زوج نقاط قطعاً فاصله‌ای بیش‌تر از dist= min(dLmin, dRmin) ندارد. پس کافی‌ست برای هر نقطه در سمت چپ خط جدا کننده،کافی است نقاطی را که در مستطیلی به ابعاد(dist, 2 ⋅ dist) در سمت راست خط جدا کننده قرار دارند را بررسی کنیم که در شکل نیز نمایش داده‌شده است.به علاوه این مستطیل حداکثر 6 نقطه می‌تواند در خود جای دهد که حداکثر فاصله‌شان dRmin است.بنابراین تعداد بهینه‌ی محاسبات در مرحله‌ی 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 این روش‌ها مناسب نیستند.

یادداشت‌ها[ویرایش]

  1. ۱٫۰ ۱٫۱ 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)
  2. S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979
  3. S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995
  4. Richard Lipton (24 September 2011). "Rabin Flips a Coin". 

جستارهای وابسته[ویرایش]

منابع[ویرایش]