এই সমস্যায়, ২ডি প্লেনে n সংখ্যক পয়েন্ট দেওয়া থাকে। আমাদের কাজ হলো এমন পয়েন্টের জোড়া খুঁজে বের করা যাদের মধ্যে দূরত্ব ন্যূনতম।
এটি সমাধান করতে পয়েন্টগুলোকে দুটি Halbfে ভাগ করতে হবে, তারপর রিকারসিভভাবে দুটি পয়েন্টের মধ্যে ন্যূনতম দূরত্ব গণনা করতে হবে। মিডলাইন থেকে দূরত্ব ব্যবহার করে পয়েন্টগুলোকে কিছু স্ট্রিপে ভাগ করা হয়। স্ট্রিপ অ্যারে থেকে ন্যূনতম দূরত্ব বের করা হয়। প্রথমে দুটি লিস্ট তৈরি করা হয় ডেটা পয়েন্টসহ, একটি লিস্ট x ভ্যালু অনুযায়ী সর্ট করা পয়েন্ট ধারণ করবে, আরেকটি y ভ্যালু অনুযায়ী সর্ট করা পয়েন্ট ধারণ করবে।
এই অ্যালগরিদমের সময় জটিলতা O(n log n)।
ইনপুট এবং আউটপুট
ইনপুট: ভিন্ন পয়েন্টের একটি সেট দেওয়া আছে। (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4) আউটপুট: প্রদত্ত পয়েন্টের প্রতিটি জোড়া থেকে ন্যূনতম দূরত্ব খুঁজে বের করুন। এখানে ন্যূনতম দূরত্ব: 1.41421 ইউনিট
এলগরিদম
findMinDist(pointsList, n)
ইনপুট: প্রদত্ত পয়েন্ট লিস্ট এবং লিস্টে পয়েন্টের সংখ্যা।
আউটপুট: দুটি পয়েন্ট থেকে ন্যূনতম দূরত্ব খুঁজে বের করে।
শুরু
min := ∞
pointsList-এ সব আইটেম i এর জন্য, করুন
j := i+1 থেকে n-1 পর্যন্ত, করুন
যদি pointList[i] এবং pointList[j]-এর মধ্যে দূরত্ব < min, তবে
min = pointList[i] এবং pointList[j]-এর দূরত্ব
শেষ লুপ
শেষ লুপ
return min
শেষ
stripClose(strips, size, dist)
ইনপুট: স্ট্রিপে ভিন্ন পয়েন্ট, পয়েন্টের সংখ্যা, মিডলাইন থেকে দূরত্ব।
আউটপুট: একটি স্ট্রিপে দুটি পয়েন্ট থেকে ন্যূনতম দূরত্ব।
শুরু
স্ট্রিপে সব আইটেম i এর জন্য, করুন
j := i+1 থেকে size-1 এবং (i-তম এবং j-তম পয়েন্টের y-ডিফারেন্স) < min, করুন
যদি strip[i] এবং strip[j]-এর মধ্যে দূরত্ব < min, তবে
min = strip[i] এবং strip[j]-এর দূরত্ব
শেষ লুপ
শেষ লুপ
return min
শেষ
findClosest(xSorted, ySorted, n)
ইনপুট: x ভ্যালু অনুযায়ী সর্ট করা পয়েন্ট, y ভ্যালু অনুযায়ী সর্ট করা পয়েন্ট, পয়েন্টের সংখ্যা।
আউটপুট: মোট পয়েন্ট সেট থেকে ন্যূনতম দূরত্ব খুঁজে বের করুন।
শুরু
যদি n <= 3, তবে
findMinDist(xSorted, n) কল করুন
ফলাফল ফেরত দিন
mid := n/2
midpoint := xSorted[mid]
দుটি সাব-লিস্ট সংজ্ঞায়িত করুন পয়েন্টগুলোকে ভার্টিক্যাল লাইন অনুযায়ী আলাদা করতে।
সাব-লিস্টগুলো হলো: ySortedLeft এবং ySortedRight
leftDist := findClosest(xSorted, ySortedLeft, mid) // বাম দূরত্ব খুঁজুন
rightDist := findClosest(xSorted, ySortedRight, n-mid) // ডান দূরত্ব খুঁজুন
dist := leftDist এবং rightDist-এর ন্যূনতম
পয়েন্টের স্ট্রিপ তৈরি করুন
j := 0
i := 0 থেকে n-1 পর্যন্ত, করুন
যদি ySorted[i].x এবং midPoint.x-এর ডিফারেন্স < dist, তবে
strip[j] := ySorted[i]
j := j+1
শেষ লুপ
close := stripClose(strip, j, dist)
return close এবং dist-এর ন্যূনতম
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct point {
int x, y;
};
int cmpX(point p1, point p2) {
// x ভ্যালু অনুযায়ী সর্ট করতে
return (p1.x < p2.x);
}
int cmpY(point p1, point p2) {
// y ভ্যালু অনুযায়ী সর্ট করতে
return (p1.y < p2.y);
}
float dist(point p1, point p2) {
// p1 এবং p2-এর মধ্যে দূরত্ব খুঁজে বের করুন
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
float findMinDist(point pts[], int n) {
// একটি সেটে দুটি পয়েন্টের মধ্যে ন্যূনতম দূরত্ব খুঁজে বের করুন
float min = 9999;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(pts[i], pts[j]) < min)
min = dist(pts[i], pts[j]);
return min;
}
float min(float a, float b) {
return (a < b)? a : b;
}
float stripClose(point strip[], int size, float d) {
// একটি স্ট্রিপে দুটি পয়েন্টের নিকটতম দূরত্ব খুঁজে বের করুন
float min = d;
for (int i = 0; i < size; ++i)
for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
if (dist(strip[i], strip[j]) < min)
min = dist(strip[i], strip[j]);
return min;
}
float findClosest(point xSorted[], point ySorted[], int n){
if (n <= 3)
return findMinDist(xSorted, n);
int mid = n/2;
point midPoint = xSorted[mid];
point ySortedLeft[mid+1]; // বাম পাশের y সর্ট করা পয়েন্ট
point ySortedRight[n-mid-1]; // ডান পাশের y সর্ট করা পয়েন্ট
int leftIndex = 0, rightIndex = 0;
for (int i = 0; i < n; i++) {
// y সর্ট করা পয়েন্টকে বাম এবং ডানে আলাদা করুন
if (ySorted[i].x <= midPoint.x)
ySortedLeft[leftIndex++] = ySorted[i];
else
ySortedRight[rightIndex++] = ySorted[i];
}
float leftDist = findClosest(xSorted, ySortedLeft, mid);
float rightDist = findClosest(ySorted + mid, ySortedRight, n-mid);
float dist = min(leftDist, rightDist);
point strip[n]; // ভার্টিক্যাল লাইনের কাছে থাকা পয়েন্ট ধারণ করুন
int j = 0;
for (int i = 0; i < n; i++)
if (abs(ySorted[i].x - midPoint.x) < dist) {
strip[j] = ySorted[i];
j++;
}
return min(dist, stripClose(strip, j, dist));
// dist এবং স্ট্রিপের ক্লোসেস্ট পেয়ার ব্যবহার করে ন্যূনতম খুঁজে বের করুন
}
float closestPair(point pts[], int n) {
// পয়েন্টের একটি সেটে ক্লোসেস্ট পেয়ারের দূরত্ব খুঁজে বের করুন
point xSorted[n];
point ySorted[n];
for (int i = 0; i < n; i++) {
xSorted[i] = pts[i];
ySorted[i] = pts[i];
}
sort(xSorted, xSorted+n, cmpX);
sort(ySorted, ySorted+n, cmpY);
return findClosest(xSorted, ySorted, n);
}
int main() {
point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
int n = 6;
cout << "The minimum distance is " << closestPair(P, n);
}
আউটপুট
The minimum distance is 1.41421
