পয়েন্টের সবচেয়ে কাছের জোড়া সমস্যা

এই সমস্যায়, 2D সমতলে n পয়েন্টের একটি সেট দেওয়া হয়। এই সমস্যায়, আমাদের বিন্দুর জোড়া খুঁজে বের করতে হবে, যার দূরত্ব সর্বনিম্ন।

এই সমস্যাটি সমাধান করার জন্য, আমাদের পয়েন্টগুলিকে দুটি অর্ধে ভাগ করতে হবে, তারপরে দুটি বিন্দুর মধ্যে ক্ষুদ্রতম দূরত্বটি পুনরাবৃত্তিমূলক উপায়ে গণনা করা হয়। মধ্যরেখা থেকে দূরত্ব ব্যবহার করে, বিন্দুগুলিকে কিছু স্ট্রিপে বিভক্ত করা হয়। আমরা স্ট্রিপ অ্যারে থেকে সবচেয়ে ছোট দূরত্ব খুঁজে পাব। প্রথমে দুটি তালিকা ডেটা পয়েন্ট দিয়ে তৈরি করা হয়, একটি তালিকা পয়েন্টগুলি ধরে রাখবে যা x মানের উপর বাছাই করা হয়, অন্যটি y মানের উপর সাজানো ডেটা পয়েন্ট ধারণ করে।

এই অ্যালগরিদমের সময় জটিলতা হবে O(n log n).

ইনপুট এবং আউটপুট

ইনপুট:বিভিন্ন পয়েন্টের একটি সেট দেওয়া হয়েছে। (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4) আউটপুট:প্রদত্ত পয়েন্টগুলির প্রতিটি জোড়া থেকে সর্বনিম্ন দূরত্ব খুঁজুন। এখানে সর্বনিম্ন দূরত্ব হল:1.41421 ইউনিট

অ্যালগরিদম

findMinDist(pointsList, n)

ইনপুট: প্রদত্ত পয়েন্ট তালিকা এবং তালিকায় পয়েন্ট সংখ্যা।

আউটপুট - দুই বিন্দু থেকে ন্যূনতম দূরত্ব খুঁজে বের করে।

 শুরু করুন min :=∞ পয়েন্টলিস্টে থাকা সমস্ত আইটেমের জন্য, j :=i+1 থেকে n-1 এর জন্য করুন, করুন যদি পয়েন্টলিস্ট[i] এবং পয়েন্টলিস্ট [j] <মিনিটের মধ্যে দূরত্ব থাকে, তাহলে মিনিট =এর দূরত্ব pointList[i] এবং pointList[j] সম্পন্ন হয়েছে রিটার্ন minEnd

স্ট্রিপ ক্লোজ(স্ট্রিপ, সাইজ, ডিস্ট)

ইনপুট - স্ট্রিপের বিভিন্ন বিন্দু, বিন্দুর সংখ্যা, মধ্যরেখা থেকে দূরত্ব।

আউটপুট - একটি স্ট্রিপে দুটি বিন্দু থেকে নিকটতম দূরত্ব৷

শুরু করুন যদি n <=3, তারপর findMinDist(xSorted, n) কল করুন ফলাফল mid :=n/2 মিডপয়েন্ট :=xSorted[mid] উল্লম্ব রেখা বরাবর পৃথক বিন্দুতে বিন্দুর দুটি উপ তালিকা সংজ্ঞায়িত করুন। সাব লিস্টগুলি হল, ySortedLeft এবং ySortedRight leftDist :=FindClosest(xSorted, ySortedLeft, mid) //find বাম দূরত্ব rightDist :=findClosest(xSorted, ySortedRight, n - mid) //find right দুরত্ব dist of left and min rightDist i :=0 থেকে n-1 এর জন্য j :=0 পয়েন্টের স্ট্রিপ তৈরি করুন, যদি ySorted[i].x এবং midPoint.x 
উদাহরণ
 
#include #include#includeNamespace ব্যবহার করে (p1.x  
আউটপুট
 
সর্বনিম্ন দূরত্ব হল 1.41421