تعیین نزدیکترین زوج نقاط در فضای دو بعدی کیست؟ توضیح بده.
مسئله نزدیکترین زوج نقاط یا نزدیکترین زوج یک مسئله از هندسه محاسباتی است که در آن در فضای متری n نقطه به عنوان ورودی گرفته می‌شود و زوج نقطه‌ای که کوتاه‌ترین فاصله بین آن‌دو وجود دارد، پیدا می‌شود. مسئله نزدیکترین زوج برای نقاط در صفحهٔ اقلیدسی از اولین مسائل هندسه بود که مطالعات سیستماتیک در نظریه پیچیدگی محاسباتی، الگوریتم‌های هندسه شد.الگوریتم ساده، پیدا کردن فاصلهٔ همهٔ زوج نقاط و انتخاب کمینهٔ آن‌هاست که نیازمند زمانی از مرتبهٔ formula_1است. به نظر می‌رسد مسئله در زمان formula_2در فضای اقلیدسی با بعد ثابت formula_3قابل حل باشد. در درخت تصمیم جبری مدل محاسبه الگوریتم با زمان formula_4با توجه به کاهشی از مساله یکتایی عنصر بهینه است. در مدل محاسباتی چنین فرض می‌شود که تابع کف در زمان ثابت قابل محاسبه است و مساله می‌تواند در formula_5حل شود. اگر در تابع کف از حالت تصادفی استفاده کنیم مسئله در formula_6نیز قابل حل است.جستجوی جامع.نزدیکترین زوج از نقاط با استتفاده از جستجوی جامع در نظریه پیچیدگی محاسباتی formula_7قابل محاسبه است. برای این کار باید فاصلهٔ میان تمامformula_8 زوج نقطه را محاسبه کرده و زوجی را که کم‌ترین فاصله را دارند، انتحاب کنیم. شبه کد این الگوریتم در زیرمشاهده می‌شود.minDist = infinityfor i = 1 to length(P) - 1 for j = i + 1 to length(P) let p = P[i], q = P[j] if dist(p, q) &lt; minDist: minDist = dist(p, q) closestPair = (p, q)return closestPairحالت صفحه.مسئله با استفاده از الگوریتم تقسیم و حل در زمان formula_9قابل حل است. رویه در زیر قابل مشاهده است.به نظر می‌رسد مرحلهٔ ۴ در زمان خطی انجام پذیرد. بار دیگر روش ساده برای این کار نیاز به محاسبهٔ فاصلهٔ همهٔ زوج نقاط در چپ و راست است که نیازمند زمان از مرتبهٔ formula_7 است. نکتهٔ اصلی در خاصیت پراکندگی مجموعهٔ نقاط است. می‌دانیم که نزدیک‌ترین زوج نقاط قطعاً فاصله‌ای بیش‌تر از formula_19 ندارد. پس کافی‌ست برای هر نقطه در سمت چپ خط جدا کننده، کافی است نقاطی را که در مستطیلی به ابعادformula_20 در سمت راست خط جدا کننده قرار دارند را بررسی کنیم که در شکل نیز نمایش داده‌شده است. به علاوه این مستطیل حداکثر ۶ نقطه می‌تواند در خود جای دهد که حداکثر فاصله‌شان formula_12 است؛ بنابراین تعداد بهینهٔ محاسبات در مرحلهٔ ۴، حداکثر محاسبه‌ی formula_22بین زوج نقاطی که یکی‌شان در سمت چپ و دیگری در سمت راست خط جدا کننده است. رابطهٔ بازگشتی برقرار بین مراحل بالا formula_23 است که با استفاده از قضیه اصلی واکاوی الگوریتم‌ها داریم:formula_2.همانند مسئله نزدیکترین زوج نقاط، یالی را در مثلث‌بندی دیلانی تعریف می‌کنیم که برابر دو خانهٔ مجاور در دیاگرام ورونوی است. نزدیک‌ترین زوج نقاط را با استفاده از دوساختار بالا می‌توان در زمان خطی محاسبه کرد. هزینه ایجاد دو ساختارمثلث‌بندی دیلانی یا دیاگرام ورونوی از لحاظ محاسباتیformula_2 است. در حالی که ره‌یافت تقسیم و حل برای تمام ابعاد هزینهٔ محاسباتی ثابتی برابر formula_2 دارد، این روش‌ها برای بعدهای بیش از ۲ این روش‌ها مناسب نیستند.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; 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; 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