ডিভাইড অ্যান্ড কঙ্কার৮ মিনিট পড়া

ক্লোজেস্ট পেয়ার অফ পয়েন্টস (Closest Pair of Points)

একটি মানচিত্রে সবচেয়ে কাছের দুটি শহর খুঁজে বের করুন — প্রতিটি জোড়া পরিমাপ না করেই বা না মেপেই
naive:ধীরগতির (Slow) · \(O(n^2)\)divide & conquer:দ্রুতগতির (Fast) · \(O(n \log n)\)space:লিনিয়ার (Linear) · \(O(n)\)

ধরুন আপনার কাছে একটি মানচিত্র বা ম্যাপ আছে যেখানে শত শত শহর ছড়িয়ে ছিটিয়ে রয়েছে, এবং আপনি এর মধ্যে থেকে সবচেয়ে কাছের দুটি শহর (two closest cities) খুঁজে বের করতে চাইছেন। এর একটি অলস বা লেইজি পদ্ধতি (lazy approach) হতে পারে: সম্ভাব্য প্রতিটি জোড়া পরিমাপ করা বা মেপে দেখা। ১,০০০টি শহরের ক্ষেত্রে এটি হবে ৫০০,০০০ বা ৫ লক্ষ পরিমাপ। এক মিলিয়ন বা দশ লক্ষ শহরের ক্ষেত্রে? হাফ ট্রিলিয়ন বা ৫০০ বিলিয়ন। এটি অতিমাত্রায় ধীরগতির।

এর স্মার্ট বা বুদ্ধিমান পদ্ধতিটি ম্যাপটিকে বা মানচিত্রটিকে অর্ধেক করে বা দু'ভাগ করে দেয়, প্রতিটি অর্ধাংশের বা অর্ধেক অংশের আলাদাভাবে সমাধান করে, তারপর খুব চালাকির সাথে বা চতুরতার সাথে সেগুলোকে একত্রিত বা মার্জ (merge) করে — এবং এটি মাত্র \(O(n \log n)\) সময়ে শেষ হয়, যা মূলত সর্টিং বা সাজানোর সমান গতির। চলুন দেখে নেওয়া যাক এটি কীভাবে কাজ করে।

লেইজি বা সাধারণ পদ্ধতি (The Naive Way) — \(O(n^2)\)

প্রতিটি জোড়া (i, j) পরীক্ষা করে বা চেক করে দেখুন এবং সবচেয়ে ছোট দূরত্বের বা শর্টেস্ট ডিসট্যান্সের ট্র্যাক বা হিসাব রাখুন। এটি অতি সাধারণ একটি উপায় এবং সঠিকও বটে, কিন্তু বড় ইনপুটগুলোর ক্ষেত্রে এটি খুব যন্ত্রণাদায়কভাবে ধীরগতির (painfully slow)। তাই আমাদের আরও স্মার্ট বা বুদ্ধিমান কিছু দরকার।

ডিভাইড অ্যান্ড কঙ্কার (Divide & Conquer) — মূল ধারণাটি

ধাপ ১ — ভাগ করা (Divide): x-স্থানাঙ্ক বা কো-অর্ডিনেট (x-coordinate) অনুযায়ী সমস্ত পয়েন্ট বা বিন্দুগুলোকে সাজিয়ে বা সর্ট করে নিন। এবার মধ্যমা বা মিডিয়ানের (median) বরাবর একটি উলম্ব (vertical) বা খাড়া রেখা আঁকুন বা টানুন, যা এই পয়েন্টগুলোর সেটকে বা অংশকে একটি বাম অর্ধেক \(L\) এবং একটি ডান অর্ধেকের \(R\) অংশে বিভক্ত করে।

ধাপ ২ — জয় করা (Conquer): রিকার্সিভলি (Recursively) বা পুনরাবৃত্তিমূলকভাবে \(L\)-এর সবচেয়ে কাছের জোড়া বা ক্লোজেস্ট পেয়ার (যার দূরত্ব \(\delta_L\)) এবং \(R\)-এর সবচেয়ে কাছের জোড়া (যার দূরত্ব \(\delta_R\)) খুঁজে বের করুন। ধরে নেই, \(\delta = \min(\delta_L, \delta_R)\)। এখন আমরা প্রতিটি অর্ধাংশের ভিতরে থাকা সেরা উত্তরটি জানি।

ধাপ ৩ — একত্র করা (Combine): বিভাজন রেখা বা ডিভাইডিং লাইনের (dividing line) দুই পাশে ছড়িয়ে থাকা বা স্ট্র্যাডেল করা (straddles) কোনো জোড়া কি \(\delta\)-কে হারাতে বা পিছনে ফেলতে পারে? সেটি কেবল তখনই সম্ভব যদি উভয় পয়েন্ট বা বিন্দুই রেখা থেকে \(\delta\) এর দূরত্বের মধ্যে থাকে — অন্যথায় শুধু তাদের অনুভূমিক ব্যবধানই বা হরিজন্টাল গ্যাপই (horizontal gap) \(\delta\) কে অতিক্রম করে যাবে। আমাদের শুধুমাত্র এই পাতলা উলম্ব স্ট্রিপটি বা খাড়া লম্বা অংশটি (vertical strip) চেক বা পরীক্ষা করলেই চলবে।

স্ট্রিপের জাদু — কেন শুধুমাত্র ৭ জন প্রতিবেশী? (Why Only 7 Neighbors)

স্ট্রিপটি বা ফালি অংশটির কথা বিবেচনা করুন: বিভাজন রেখা বা ডিভাইডিং লাইন থেকে δ দূরত্বের মধ্যে থাকা পয়েন্টসমূহ বা বিন্দুগুলো, যেগুলো y-স্থানাঙ্ক বা কো-অর্ডিনেট (y-coordinate) দ্বারা সাজানো। স্ট্রিপের যেকোনো \(\delta \times 2\delta\) আয়তক্ষেত্রের (rectangle) মধ্যে, সর্বোচ্চ বা বড়জোর 8টি পয়েন্ট থাকতে পারে। কিন্তু কেন? সেই আয়তক্ষেত্রটির প্রতিটি অর্ধেক বা ভাগ হলো একটি করে \(\delta \times \delta\) বর্গক্ষেত্র। একই অর্ধাংশে বা অর্ধেকের মধ্যে থাকা যেকোনো দুটি পয়েন্টের বা বিন্দুর দূরত্ব বা ব্যবধান \(\ge \delta\) (যেহেতু আমরা ইতিপূর্বেই প্রতিটি অর্ধাংশের সেরা দূরত্বটি খুঁজে পেয়েছি)। এই শর্তের অধীনে আপনি একটি \(\delta \times \delta\) বর্গক্ষেত্রে বড়জোর 4 টি পয়েন্টকে (points) রাখতে বা আটকাতে পারবেন। সুতরাং, দুটি বর্গক্ষেত্র মিলিয়ে → সর্বমোট সর্বোচ্চ 8 টি পয়েন্ট।

তাই এই স্ট্রিপ বা ফালির মধ্যে থাকা প্রতিটি পয়েন্ট বা বিন্দুর জন্য, আপনাকে শুধু একে y-অর্ডার বা y এর ক্রমানুসারে পরবর্তী 7 টি পয়েন্টের সাথে তুলনা (compare) করলেই চলবে। এটি মূলত স্ট্রিপ স্ক্যানটিকে \(O(n)\)-এ পরিণত করে দেয় — \(O(n^2)\)-এ নয়!

পদ্ধতিটিকে \(O(n \log n)\)-এ রূপান্তর

আপনি যদি প্রতিটি রিকার্সিভ (recursive) স্তরে বা লেভেলে স্ট্রিপটিকে y দ্বারা সাজান বা সর্ট করেন, তবে এর একত্রীকরণ বা কম্বাইন (combine) ধাপে \(O(n \log n)\) খরচ হয়, যা T(n) = 2T(n/2) + \(O(n \log n)\) → \(O(n \log^2 n)\) দেয়। কিন্তু আপনি যদি রিকার্সন (recursion) চালানোর আগেই বা রিকার্সিং এর পূর্বেই সমস্ত পয়েন্ট বা বিন্দুগুলোকে একবার (once) y দ্বারা সর্ট বা প্রি-সর্ট করে নেন (ঠিক যেভাবে মার্জ সর্ট বা merge sort তার মার্জিং (merging) এর সময় একটি সাজানো বা সর্টেড তালিকা বজায় রাখে), তখন স্ট্রিপ স্ক্যানটি \(O(n)\) হয়ে যায়। এখন T(n) = 2T(n/2) + \(O(n)\) → \(O(n \log n)\). এটি একেবারেই মার্জ সর্টের (merge sort) মতো একই কৌশল বা ট্রিক (trick)!

দ্রষ্টব্য: এই স্ট্রিপ বা ফালিটিতে যেকোনো \(\delta \times 2\delta\) বক্সের বা বাক্সের মধ্যে শুধুমাত্র 8টি পয়েন্ট বা বিন্দু থাকতে পারে — এটি একটি প্যাকিং আর্গুমেন্ট (packing argument)। এটি মূলত এমন একটি বিষয় যা \(O(n^2)\) স্ট্রিপ স্ক্যানটিকে পরিবর্তন করে \(O(n)\)-এ পরিণত করে। এখানকার জ্যামিতি বা জিওমেট্রিই (geometry) মূলত সব ভারী বা আসল কাজটি করে দেয়।

সবচেয়ে কাছের জোড়া (Closest Pair) — ডিভাইড অ্যান্ড কঙ্কার বা ভাগ করুন ও জয় করুন

import math


def dist(p, q):
    return math.hypot(p[0]-q[0], p[1]-q[1])


def strip_closest(strip, d):
    best = d
    strip.sort(key=lambda p: p[1])
    for i in range(len(strip)):
        j = i + 1
        while j < len(strip) and strip[j][1] - strip[i][1] < best:
            best = min(best, dist(strip[i], strip[j]))
            j += 1
    return best


def closest(pts):
    pts.sort()
    def rec(P):
        if len(P) <= 3:
            best = float('inf')
            for i in range(len(P)):
                for j in range(i+1, len(P)):
                    best = min(best, dist(P[i], P[j]))
            return best
        mid = len(P) // 2
        midX = P[mid][0]
        d = min(rec(P[:mid]), rec(P[mid:]))
        strip = [p for p in P if abs(p[0] - midX) < d]
        return min(d, strip_closest(strip, d))
    return rec(pts)


points = [(2,3),(5,1),(1,6),(8,9),(3,7),(4,2)]
print(f"{closest(points):.4f}")  # 2.2361
Output
2.2361

Complexity

🐢 লেইজি অল-পেয়ার বা সমস্ত জোড়া চেক (Naive all-pairs check)
n পয়েন্টের বা বিন্দুর প্রতিটি জোড়া চেক বা পরীক্ষা করে দেখা হয় — যা বড় n এর জন্য ব্যবহার অযোগ্য বা অনুপযুক্ত
কোয়াড্রাটিক বা দ্বিঘাতী (Quadratic) \(O(n^2)\)
📐 প্রি-সর্ট ছাড়া D&C (D&C without pre-sort)
প্রতিটি স্তরে বা লেভেলে স্ট্রিপটিকে বা ফালিটিকে y দ্বারা পুনরায় সর্ট বা সাজানো হলে একটি অতিরিক্ত লগ ফ্যাক্টর (log factor) যোগ হয়
প্রায়-লিনিয়ারিদমিক (Near-linearithmic) \(O(n \log^2 n)\)
🚀 প্রি-সর্ট করা y এর তালিকার সাথে D&C (D&C with pre-sorted y list)
রিকার্সিভ কলগুলোর (recursive calls) মধ্য দিয়ে গ্লোবাল বা সামগ্রিক y-অর্ডার বজায় রাখে; যেখানে স্ট্রিপ স্ক্যান হলো \(O(n)\)
লিনিয়ারিদমিক (Linearithmic) \(O(n \log n)\)
📦 স্পেস বা মেমরি (Space)
সাজানো বা সর্টেড তালিকা এবং স্ট্রিপ বা ফালির ক্যান্ডিডেটদের বা প্রাপ্ত মানগুলোর জন্য স্ক্র্যাচ অ্যারেগুলো (Scratch arrays)
অক্সিলিয়ারি লিনিয়ার (Auxiliary Linear) \(O(n)\)
🔎 প্রতিটি পয়েন্ট বা বিন্দুতে স্ট্রিপ স্ক্যান (Strip scan per point)
প্যাকিং আর্গুমেন্ট (Packing argument): \(\delta \times 2\delta\) বক্সে বা বাক্সে ≤ 8টি পয়েন্ট বা বিন্দু অবস্থান করতে পারে বা রাখা যায়
ধ্রুবক বা কন্সট্যান্ট (Constant) \(O(1)\) — সর্বোচ্চ ৭ জন প্রতিবেশী

ছোট কুইজ

কেন আমরা শুধুমাত্র ডিভাইডিং লাইন বা বিভাজন রেখার \(\delta\) দূরত্বের মধ্যে থাকা পয়েন্টগুলোকেই স্ট্রিপে বা ফালিতে পরীক্ষা করি বা চেক করি?

পড়া চালিয়ে যান

ডিভাইড অ্যান্ড কঙ্কার (D&C) প্যাটার্ন (Divide and Conquer Pattern)
সমস্যাটিকে ছোট ছোট টুকরাতে বিভক্ত করুন, টুকরোগুলোকে সমাধান করুন এবং তারপর সব ফলাফলগুলোকে একত্রিত করুন
→
মার্জ সর্ট (Merge Sort)
ভাগ করুন, প্রতি অর্ধেক সাজান, তারপর একত্রিত (merge) করুন — প্রতিবারই \(O(n \log n)\) এর নিশ্চয়তা
→
রিকারেন্স রিলেশন (Recurrence Relations)
নিজে নিজেকে ডাকা একটি রেসিপি — সমাধান করতে পারার মতো সহজ না হওয়া পর্যন্ত
→