মিনিমাম এনক্লোজিং সার্কেল#

নিচের সমস্যাটি বিবেচনা করুন:

নিচের যুক্তি আরও ভালোভাবে বোঝার জন্য, আমাদের তৎক্ষণাৎ লক্ষ্য করা উচিত যে এই সমস্যার সমাধান অনন্য:

ওয়েলজল অ্যালগরিদম#

সংক্ষিপ্ততার জন্য, $\operatorname{mec}(p_1,\dots,p_n)$ দিয়ে $\{p_1,\dots,p_n\}$-এর MEC বোঝাই, এবং $P_i = \{p_1,\dots,p_i\}$ ধরি।

ওয়েলজল ১৯৯১ সালে প্রথম প্রস্তাবিত এই অ্যালগরিদমটি নিম্নরূপ:

১. ইনপুট বিন্দুগুলোর ক্রমানুসারে একটি র‍্যান্ডম পারমুটেশন প্রয়োগ করুন। ২. বর্তমান MEC প্রার্থী $C$ বজায় রাখুন, $C = \operatorname{mec}(p_1, p_2)$ দিয়ে শুরু করে। ৩. $i=3..n$ পর্যন্ত ইটারেট করুন এবং পরীক্ষা করুন $p_i \in C$ কি না। ১. যদি $p_i \in C$ হয় তাহলে $C$ হলো $P_i$-এর MEC। ২. অন্যথায়, $C = \operatorname{mec}(p_i, p_1)$ নির্ধারণ করুন এবং $j=2..i$ পর্যন্ত ইটারেট করে পরীক্ষা করুন $p_j \in C$ কি না। ১. যদি $p_j \in C$ হয়, তাহলে $C$ হলো $P_j$-এর MEC যা $p_i$-এর মধ্য দিয়ে যায়। ২. অন্যথায়, $C=\operatorname{mec}(p_i, p_j)$ নির্ধারণ করুন এবং $k=1..j$ পর্যন্ত ইটারেট করে পরীক্ষা করুন $p_k \in C$ কি না। ১. যদি $p_k \in C$ হয়, তাহলে $C$ হলো $P_k$-এর MEC যা $p_i$ ও $p_j$-এর মধ্য দিয়ে যায়। ২. অন্যথায়, $C=\operatorname{mec}(p_i,p_j,p_k)$ হলো $P_k$-এর MEC যা $p_i$ ও $p_j$-এর মধ্য দিয়ে যায়।

আমরা দেখতে পাচ্ছি যে নেস্টেডনেসের প্রতিটি স্তরে এখানে একটি ইনভ্যারিয়েন্ট বজায় রাখতে হয় (যে $C$ হলো MEC যা অতিরিক্তভাবে প্রদত্ত $0$, $1$ বা $2$ টি বিন্দুর মধ্য দিয়ে যায়), এবং যখনই ভেতরের লুপ শেষ হয়, এর ইনভ্যারিয়েন্ট প্যারেন্ট লুপের বর্তমান ইটারেশনের ইনভ্যারিয়েন্টের সমতুল্য হয়ে যায়। এটি, পরিবর্তে, সামগ্রিকভাবে অ্যালগরিদমের সঠিকতা নিশ্চিত করে।

আপাতত কিছু টেকনিক্যাল বিবরণ বাদ দিয়ে, পুরো অ্যালগরিদমটি C++-এ নিম্নরূপে ইমপ্লিমেন্ট করা যায়:

struct point {...};

// Is represented by 2 or 3 points on its circumference
struct mec {...};

bool inside(mec const& C, point p) {
    return ...;
}

// Choose some good generator of randomness for the shuffle
mt19937_64 gen(...);
mec enclosing_circle(vector<point> &p) {
    int n = p.size();
    ranges::shuffle(p, gen);
    auto C = mec{p[0], p[1]};
    for(int i = 0; i < n; i++) {
        if(!inside(C, p[i])) {
            C = mec{p[i], p[0]};
            for(int j = 0; j < i; j++) {
                if(!inside(C, p[j])) {
                    C = mec{p[i], p[j]};
                    for(int k = 0; k < j; k++) {
                        if(!inside(C, p[k])) {
                            C = mec{p[i], p[j], p[k]};
                        }
                    }
                }
            }
        }
    }
    return C;
}

এখন, এটা আশা করা যায় যে একটি বিন্দু $p_i$ $2$ বা $3$ টি বিন্দুর MEC-এর ভেতরে কি না তা $O(1)$-এ পরীক্ষা করা যায় (এটি আমরা পরে আলোচনা করব)। কিন্তু তারপরও, উপরের অ্যালগরিদমটি দেখে মনে হয় শুধু নেস্টেড লুপগুলোর কারণে সবচেয়ে খারাপ ক্ষেত্রে $O(n^3)$ লাগবে। তাহলে আমরা কীভাবে লিনিয়ার প্রত্যাশিত রানটাইম দাবি করলাম? চলুন জেনে নিই!

কমপ্লেক্সিটি বিশ্লেষণ#

সবচেয়ে ভেতরের লুপের জন্য ($k$-এর উপর), স্পষ্টতই এর প্রত্যাশিত রানটাইম হলো $O(j)$ অপারেশন। $j$-এর উপর লুপটির ক্ষেত্রে কী হবে?

এটি শুধুমাত্র তখনই পরবর্তী লুপ ট্রিগার করে যদি $p_j$, $P_j$-এর MEC-এর সীমানায় থাকে যা বিন্দু $i$-এর মধ্য দিয়েও যায়, এবং $p_j$ সরিয়ে ফেললে বৃত্তটি আরও ছোট হতো। $P_j$-র সব বিন্দুর মধ্যে এই বৈশিষ্ট্যসম্পন্ন সর্বাধিক $2$ টি বিন্দু থাকতে পারে, কারণ যদি সীমানায় $2$ টির বেশি বিন্দু থাকে, তাহলে তাদের যেকোনো একটি সরানোর পরেও সীমানায় অন্তত $3$ টি বিন্দু থাকবে, যা বৃত্তটিকে অনন্যভাবে নির্ধারণ করতে যথেষ্ট।

অন্য কথায়, প্রাথমিক র‍্যান্ডম শাফলের পর, $p_j$ হিসেবে সর্বাধিক দুটি দুর্ভাগ্যজনক বিন্দুর একটি পাওয়ার সম্ভাবনা সর্বাধিক $\frac{2}{j}$। $1$ থেকে $i$ পর্যন্ত সব $j$-এর উপর যোগ করলে, আমরা প্রত্যাশিত রানটাইম পাই

ঠিক একই পদ্ধতিতে আমরা এখন প্রমাণ করতে পারি যে সবচেয়ে বাইরের লুপেরও প্রত্যাশিত রানটাইম $O(n)$।

একটি বিন্দু ২ বা ৩ বিন্দুর MEC-এর মধ্যে কি না তা পরীক্ষা করা#

চলুন এখন point এবং mec-এর ইমপ্লিমেন্টেশন বিবরণ বের করি। এই সমস্যায়, std::complex কে বিন্দুর ক্লাস হিসেবে ব্যবহার করা বিশেষভাবে কার্যকর:

using ftype = int64_t;
using point = complex<ftype>;

স্মরণ করিয়ে দিই, একটি জটিল সংখ্যা হলো $x+yi$ ধরনের, যেখানে $i^2=-1$ এবং $x, y \in \mathbb R$। C++-এ, এই জটিল সংখ্যাকে একটি ২-মাত্রিক বিন্দু $(x, y)$ দ্বারা উপস্থাপন করা হয়। জটিল সংখ্যা ইতিমধ্যেই মৌলিক কম্পোনেন্ট-ভিত্তিক লিনিয়ার অপারেশনগুলো (যোগ, বাস্তব সংখ্যা দিয়ে গুণ) ইমপ্লিমেন্ট করে, তবে তাদের গুণ ও ভাগেরও নির্দিষ্ট জ্যামিতিক তাৎপর্য রয়েছে।

খুব বেশি বিস্তারিত না গিয়ে, আমরা এই নির্দিষ্ট কাজের জন্য সবচেয়ে গুরুত্বপূর্ণ বৈশিষ্ট্যটি উল্লেখ করব: দুটি জটিল সংখ্যার গুণ তাদের পোলার কোণ যোগ করে ($Ox$ থেকে ঘড়ির কাঁটার বিপরীত দিকে গণনা করা), এবং কনজুগেট নেওয়া (অর্থাৎ $z=x+yi$ কে $\overline{z} = x-yi$-তে পরিবর্তন করা) পোলার কোণকে $-1$ দিয়ে গুণ করে। এটি আমাদের $2$ বা $3$ টি নির্দিষ্ট বিন্দুর MEC-এর ভেতরে একটি বিন্দু $z$ আছে কি না তার জন্য কিছু অত্যন্ত সরল শর্ত তৈরি করতে দেয়।

২ বিন্দুর MEC#

$2$ টি বিন্দু $a$ ও $b$-এর জন্য, তাদের MEC হলো $\frac{a+b}{2}$ কেন্দ্র এবং $\frac{|a-b|}{2}$ ব্যাসার্ধ বিশিষ্ট বৃত্ত, অন্য কথায় সেই বৃত্ত যার $ab$ ব্যাস। $z$ এই বৃত্তের ভেতরে আছে কি না তা পরীক্ষা করতে আমাদের শুধু দেখতে হবে $za$ ও $zb$-এর মধ্যবর্তী কোণ সূক্ষ্ম নয়।

অন্তঃস্থ কোণগুলো স্থূলকোণ, বহিঃস্থ কোণগুলো সূক্ষ্মকোণ এবং পরিধির উপরের কোণগুলো সমকোণ

সমতুল্যভাবে, আমাদের পরীক্ষা করতে হবে যে

একটি ধনাত্মক বাস্তব স্থানাঙ্ক নেই (যা $-90^\circ$ ও $90^\circ$-এর মধ্যে পোলার কোণ বিশিষ্ট বিন্দুগুলোর সাথে সম্পর্কিত)।

৩ বিন্দুর MEC#

ত্রিভুজ $abc$-তে $z$ যোগ করলে এটি একটি চতুর্ভুজ হবে। নিম্নলিখিত রাশিটি বিবেচনা করুন:

একটি চক্রীয় চতুর্ভুজে, যদি $c$ এবং $z$ একই পাশে $ab$-এর সাপেক্ষে থাকে, তাহলে কোণগুলো সমান, এবং চিহ্নসহ (অর্থাৎ ঘড়ির কাঁটার বিপরীতে ধনাত্মক এবং ঘড়ির কাঁটার দিকে ঋণাত্মক) যোগ করলে $0^\circ$ হবে। অনুরূপভাবে, যদি $c$ ও $z$ বিপরীত পাশে থাকে, তাহলে কোণগুলোর যোগফল $180^\circ$ হবে।

পাশাপাশি অন্তর্লিখিত কোণগুলো সমান, বিপরীত কোণগুলো ১৮০ ডিগ্রি পূরক

জটিল সংখ্যার ভাষায়, আমরা লক্ষ্য করতে পারি যে $\angle azb$ হলো $(b-z)\overline{(a-z)}$-এর পোলার কোণ এবং $\angle bca$ হলো $(a-c)\overline{(b-c)}$-এর পোলার কোণ। সুতরাং, আমরা সিদ্ধান্তে পৌঁছাতে পারি যে $\angle azb + \angle bca$ হলো নিম্নলিখিতের পোলার কোণ

যদি কোণটি $0^\circ$ বা $180^\circ$ হয়, তাহলে $I_1$-এর কাল্পনিক অংশ $0$, অন্যথায় আমরা $I_1$-এর কাল্পনিক অংশের চিহ্ন পরীক্ষা করে বুঝতে পারি $z$ $abc$-এর এনক্লোজিং সার্কেলের ভেতরে না বাইরে। ধনাত্মক কাল্পনিক অংশ ধনাত্মক কোণের সাথে সম্পর্কিত, এবং ঋণাত্মক কাল্পনিক অংশ ঋণাত্মক কোণের সাথে সম্পর্কিত।

কিন্তু কোনটি বোঝায় $z$ বৃত্তের ভেতরে এবং কোনটি বাইরে? আমরা ইতিমধ্যেই লক্ষ্য করেছি, $z$ বৃত্তের ভেতরে থাকলে সাধারণত $\angle azb$-এর পরিমাণ বৃদ্ধি পায়, আর বাইরে থাকলে কমে। সুতরাং, আমাদের নিম্নলিখিত ৪টি ক্ষেত্র রয়েছে:

১. $\angle bca > 0^\circ$, $c$ এবং $z$ একই পাশে $ab$-এর সাপেক্ষে। তখন, $\angle azb < 0^\circ$, এবং বৃত্তের ভেতরের বিন্দুগুলোর জন্য $\angle azb + \angle bca < 0^\circ$। ৩. $\angle bca < 0^\circ$, $c$ এবং $z$ একই পাশে $ab$-এর সাপেক্ষে। তখন, $\angle azb > 0^\circ$, এবং বৃত্তের ভেতরের বিন্দুগুলোর জন্য $\angle azb + \angle bca > 0^\circ$। ২. $\angle bca > 0^\circ$, $c$ এবং $z$ বিপরীত পাশে $ab$-এর সাপেক্ষে। তখন, $\angle azb > 0^\circ$ এবং বৃত্তের ভেতরের বিন্দুগুলোর জন্য $\angle azb + \angle bca > 180^\circ$। ৪. $\angle bca < 0^\circ$, $c$ এবং $z$ বিপরীত পাশে $ab$-এর সাপেক্ষে। তখন, $\angle azb < 0^\circ$ এবং বৃত্তের ভেতরের বিন্দুগুলোর জন্য $\angle azb + \angle bca < 180^\circ$।

অন্য কথায়, যদি $\angle bca$ ধনাত্মক হয়, বৃত্তের ভেতরের বিন্দুগুলোর $\angle azb + \angle bca < 0^\circ$ হবে, অন্যথায় $\angle azb + \angle bca > 0^\circ$ হবে, ধরে নিচ্ছি আমরা কোণগুলো $-180^\circ$ ও $180^\circ$-এর মধ্যে নরমালাইজ করি। এটি, পরিবর্তে, $I_2=(a-c)\overline{(b-c)}$ ও $I_1 = I_0 I_2$-এর কাল্পনিক অংশের চিহ্ন দ্বারা পরীক্ষা করা যায়।

দ্রষ্টব্য: আমরা $I_1$ পেতে চারটি জটিল সংখ্যা গুণ করায়, মধ্যবর্তী সহগ $O(A^4)$ পর্যন্ত বড় হতে পারে, যেখানে $A$ হলো ইনপুটে সর্ববৃহৎ স্থানাঙ্কের পরিমাণ। ভালো দিক হলো, যদি ইনপুট পূর্ণসংখ্যা হয়, তাহলে উভয় পরীক্ষাই সম্পূর্ণ পূর্ণসংখ্যায় করা যায়।

ইমপ্লিমেন্টেশন#

এখন, আসলেই পরীক্ষাটি ইমপ্লিমেন্ট করতে, আমাদের প্রথমে ঠিক করতে হবে MEC কীভাবে রিপ্রেজেন্ট করব। যেহেতু আমাদের শর্তগুলো সরাসরি বিন্দু নিয়ে কাজ করে, একটি স্বাভাবিক ও দক্ষ উপায় হলো MEC কে সরাসরি দুই বা তিনটি বিন্দুর জোড়া বা ত্রয়ী হিসেবে রিপ্রেজেন্ট করা:

using mec = variant<
    array<point, 2>,
    array<point, 3>
>;

এখন, আমরা std::visit ব্যবহার করে উপরের শর্ত অনুযায়ী উভয় ক্ষেত্র দক্ষভাবে হ্যান্ডেল করতে পারি:

/* I < 0 if z inside C,
   I > 0 if z outside C,
   I = 0 if z on the circumference of C */
ftype indicator(mec const& C, point z) {
    return visit([&](auto &&C) {
        point a = C[0], b = C[1];
        point I0 = (b - z) * conj(a - z);
        if constexpr (size(C) == 2) {
            return real(I0);
        } else {
            point c = C[2];
            point I2 = (a - c) * conj(b - c);
            point I1 = I0 * I2;
            return imag(I2) < 0 ? -imag(I1) : imag(I1);
        }
    }, C);
}

bool inside(mec const& C, point p) {
    return indicator(C, p) <= 0;
}

এখন, আমরা Library Checker-এ সমস্যাটি সাবমিট করে সবকিছু কাজ করছে কি না নিশ্চিত হতে পারি: #308668।

অনুশীলন সমস্যা#

• Library Checker - Minimum Enclosing Circle
• BOI 2002 - Aliens