क्लोजेस्ट पेयर ऑफ पॉइंट्स समस्या

इस समस्या में, n बिंदुओं का एक समुच्चय 2D तल पर दिया जाता है। इस समस्या में, हमें बिंदुओं के उस जोड़े को खोजना है, जिनके बीच की दूरी न्यूनतम है।

इस समस्या को हल करने के लिए, हमें बिंदुओं को दो हिस्सों में विभाजित करना होगा, उसके बाद दो बिंदुओं के बीच की सबसे छोटी दूरी की गणना पुनरावर्ती तरीके से की जाती है। मध्य रेखा से दूरियों का उपयोग करके, बिंदुओं को कुछ स्ट्रिप्स में अलग किया जाता है। हम स्ट्रिप सरणी से सबसे छोटी दूरी खोजेंगे। सबसे पहले डेटा बिंदुओं के साथ दो सूचियाँ बनाई जाती हैं, एक सूची उन बिंदुओं को रखेगी जो 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] की दूरी       किया     किया     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] की दूरी       किया     किया     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)     close और dist का न्यूनतम वापस करें अंत

उदाहरण

#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