Хамгийн бага багтаах тойрог¶

Дараах бодлогыг авч үзье:

Library Checker - Minimum Enclosing Circle

Танд $n \leq 10^5$ ширхэг $p_i=(x_i, y_i)$ цэг өгөгдсөн.

$p_i$ бүрийн хувьд тэр нь $\{p_1,\dots,p_n\}$-ийн хамгийн бага багтаах тойргийн хүрээн дээр орших эсэхийг ол.

Энд хамгийн бага багтаах тойрог (MEC) гэж бид $n$ цэгийг бүгдийг нь тойргийн дотор эсвэл заагт нь агуулах боломжит хамгийн бага радиустай тойргийг хэлж байна. Энэ бодлого нь эхлээд харахад $O(n^3)$-д ажиллах мэт харагдах боловч үнэндээ $O(n)$ хүлээгдэх хугацаанд ажилладаг энгийн санамсаргүй шийдтэй.

Доорх үндэслэлийг илүү сайн ойлгохын тулд бид бодлогын шийд давтагдашгүй болохыг шууд тэмдэглэх хэрэгтэй:

MEC яагаад давтагдашгүй вэ?

Дараах бүтцийг авч үзье: $r$ нь MEC-ийн радиус байг. Бид $p_1,\dots,p_n$ цэг бүрийн эргэн тойронд $r$ радиустай тойрог зурна. Геометрийн хувьд $r$ радиустай бөгөөд $p_1,\dots,p_n$ бүх цэгийг бүрхэх тойргуудын төвүүд нь $n$ тойргийн бүгдийн огтлолцлыг үүсгэнэ.

Одоо хэрэв огтлолцол ердөө ганц цэг бол энэ нь давтагдашгүй болохыг аль хэдийн батална. Эс бөгөөс огтлолцол нь тэгээс ялгаатай талбайтай дүрс тул бид $r$-г өчүүхэн бага зэрэг багасгаад ч хоосон биш огтлолцолтой хэвээр байх ба энэ нь $r$ нь багтаах тойргийн боломжит хамгийн бага радиус байсан гэсэн таамаглалтай зөрчилдөнө.

Үүнтэй адил логикоор бид MEC өгөгдсөн тодорхой $p_i$ цэг, эсвэл $p_i$ ба $p_j$ гэсэн хоёр цэгээр дайрахыг нэмж шаардвал түүний давтагдашгүй байдлыг мөн харуулж болно (энэ нь мөн давтагдашгүй, учир нь түүний радиус түүнийг цор ганцаар тодорхойлно).

Өөр аргаар бид хоёр MEC байна гэж үзээд, дараа нь тэдгээрийн огтлолцол ($p_1,\dots,p_n$ цэгүүдийг аль хэдийн агуулж байгаа) анхны тойргуудаас бага диаметртэй байх ёстой тул илүү бага тойргоор бүрхэгдэж болохыг анзаарч болно.

Велцлийн алгоритм¶

Товчхон байхын тулд $\operatorname{mec}(p_1,\dots,p_n)$-г $\{p_1,\dots,p_n\}$-ийн MEC гэж тэмдэглээд $P_i = \{p_1,\dots,p_i\}$ гэж авъя.

1991 онд Welzl-ийн анх санал болгосон алгоритм дараах байдалтай:

Цэгүүдийн оролтын дараалалд санамсаргүй сэлгэмэл хэрэглэ.
MEC-ийн одоогийн нэр дэвшигч $C$-г хөтөл, $C = \operatorname{mec}(p_1, p_2)$-ээс эхэл.
$i=3..n$-г тойрч $p_i \in C$ эсэхийг шалга.
1. Хэрэв $p_i \in C$ бол $C$ нь $P_i$-ийн MEC гэсэн үг.
2. Эс бөгөөс $C = \operatorname{mec}(p_i, p_1)$ гэж оноогоод $j=2..i$-г тойрч $p_j \in C$ эсэхийг шалга.
  1. Хэрэв $p_j \in C$ бол $C$ нь $p_i$-ээр дайрдаг тойргуудын дундаас $P_j$-ийн MEC болно.
  2. Эс бөгөөс $C=\operatorname{mec}(p_i, p_j)$ гэж оноогоод $k=1..j$-г тойрч $p_k \in C$ эсэхийг шалга.
    1. Хэрэв $p_k \in C$ бол $C$ нь $p_i$ ба $p_j$-ээр дайрдаг тойргуудын дундаас $P_k$-ийн MEC болно.
    2. Эс бөгөөс $C=\operatorname{mec}(p_i,p_j,p_k)$ нь $p_i$ ба $p_j$-ээр дайрдаг тойргуудын дундаас $P_k$-ийн MEC болно.

Энд үүрлэлтийн түвшин бүр хөтлөх ёстой инварианттай ($C$ нь нэмж өгөгдсөн $0$, $1$ эсвэл $2$ цэгээр мөн дайрдаг тойргуудын дундах MEC байх) бөгөөд дотоод давталт хаагдах бүрд түүний инвариант нь эцэг давталтынхаа одоогийн итерацын инварианттай эквивалент болохыг бид харж болно. Энэ нь эргээд алгоритмын бүхэлдээ зөв байдлыг баталгаажуулна.

Зарим техникийн нарийн ширийн зүйлийг одоохондоо орхиод бүхэл алгоритмыг 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)$ авах мэт харагдана. Тэгвэл бид яагаад шугаман хүлээгдэх ажиллах хугацаа гэж баталсан бэ? Тодруулъя!

Complexity-ийн шинжилгээ¶

Хамгийн дотоод давталтын (($k$-ийн хувьд) хүлээгдэх ажиллах хугацаа нь $O(j)$ үйлдэл болох нь тодорхой. $j$-ийн давталтын хувьд яах вэ?

Энэ нь зөвхөн $p_j$ нь $i$ цэгээр мөн дайрдаг $P_j$-ийн MEC-ийн зааг дээр байх, мөн $p_j$-г хасах нь тойргийг цааш нь багасгах үед л дараагийн давталтыг ажиллуулна. $P_j$ дэх бүх цэгийн дундаас ийм шинж чанартай хамгийн ихдээ $2$ цэг байж болно, учир нь хэрэв зааг дээр $P_j$-ээс $2$-оос олон цэг байвал тэдгээрийн алийг нь ч хассны дараа зааг дээр дор хаяж $3$ цэг үлдэх ба энэ нь тойргийг цор ганцаар тодорхойлоход хангалттай.

Өөрөөр хэлбэл анхны санамсаргүй холилтын дараа бид $p_j$-ээр хамгийн ихдээ хоёр азгүй цэгийн нэгийг авах магадлал хамгийн ихдээ $\frac{2}{j}$ байна. Үүнийг $1$-ээс $i$ хүртэлх бүх $j$-ийн хувьд нэмбэл бид дараах хүлээгдэх ажиллах хугацааг авна

$$ \sum\limits_{j=1}^i \frac{2}{j} \cdot O(j) = O(i). $$

Яг ижил байдлаар бид одоо хамгийн гадаад давталт $O(n)$ хүлээгдэх ажиллах хугацаатай болохыг ч батлаж болно.

Цэг 2 эсвэл 3 цэгийн MEC-д байгаа эсэхийг шалгах¶

Одоо point ба mec-ийн хэрэгжүүлэлтийн нарийн ширийнийг тодруулъя. Энэ бодлогод цэгүүдийн классаар std::complex-г ашиглах нь онцгой хэрэгтэй болох нь тогтоогддог:

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

Сануулахад комплекс тоо гэдэг нь $x+yi$ хэлбэрийн тоо бөгөөд энд $i^2=-1$ ба $x, y \in \mathbb R$. C++-д ийм комплекс тоог 2 хэмжээст $(x, y)$ цэгээр илэрхийлнэ. Комплекс тоонууд компонент тус бүрийн үндсэн шугаман үйлдлүүдийг (нэмэх, бодит тоогоор үржүүлэх) аль хэдийн хэрэгжүүлсэн байдаг ба түүнчлэн тэдгээрийн үржих, хуваах үйлдэл нь тодорхой геометрийн утга агуулдаг.

Хэт нарийн ширийн рүү орохгүйгээр бид энэ тодорхой бодлогын хувьд хамгийн чухал шинж чанарыг тэмдэглэе: Хоёр комплекс тоог үржүүлэх нь тэдгээрийн туйлын өнцгүүдийг ($Ox$-ээс цагийн зүүний эсрэг тоолсон) нэмнэ, мөн хосмог авах (өөрөөр хэлбэл $z=x+yi$-г $\overline{z} = x-yi$ болгож өөрчлөх) нь туйлын өнцгийг $-1$-ээр үржүүлнэ. Энэ нь бидэнд $z$ цэг $2$ эсвэл $3$ тодорхой цэгийн MEC-ийн дотор байгаа эсэхийн маш энгийн шалгуурыг томьёолох боломж олгоно.

2 цэгийн MEC¶

$a$ ба $b$ гэсэн $2$ цэгийн хувьд тэдгээрийн MEC нь зүгээр л $\frac{a+b}{2}$ төвтэй, $\frac{|a-b|}{2}$ радиустай тойрог буюу өөрөөр хэлбэл $ab$-г диаметр болгосон тойрог юм. $z$ энэ тойргийн дотор байгаа эсэхийг шалгахын тулд бид зүгээр л $za$ ба $zb$-ийн хоорондох өнцөг хурц биш эсэхийг шалгах хэрэгтэй.

Дотоод өнцгүүд мохоо, гадаад өнцгүүд хурц, тойргийн хүрээн дээрх өнцгүүд тэгш өнцөг байна

Үүнтэй эквивалентээр бид дараахыг шалгах хэрэгтэй

$$ I_0=(b-z)\overline{(a-z)} $$

эерэг бодит координатгүй байх ($-90^\circ$ ба $90^\circ$-ийн хоорондох туйлын өнцөгтэй цэгүүдэд харгалзана).

3 цэгийн MEC¶

$abc$ гурвалжинд $z$-г нэмбэл дөрвөн өнцөгт болно. Дараах илэрхийллийг авч үзье:

$$ \angle azb + \angle bca $$

Тойрогт багтсан дөрвөн өнцөгтөд хэрэв $c$ ба $z$ нь $ab$-ийн нэг талд байвал өнцгүүд тэнцүү байх ба тэмдэгтэй нь нэмбэл $0^\circ$ болно (өөрөөр хэлбэл цагийн зүүний эсрэг бол эерэг, цагийн зүүний дагуу бол сөрөг). Үүний дагуу хэрэв $c$ ба $z$ эсрэг талуудад байвал өнцгүүд нэмэгдээд $180^\circ$ болно.

Зэргэлдээ багтсан өнцгүүд ижил, эсрэг талын өнцгүүд нийлээд 180 градус болно

Комплекс тоогоор илэрхийлбэл $\angle azb$ нь $(b-z)\overline{(a-z)}$-ийн туйлын өнцөг, $\angle bca$ нь $(a-c)\overline{(b-c)}$-ийн туйлын өнцөг болохыг анзаарч болно. Ингэснээр бид $\angle azb + \angle bca$ нь дараахын туйлын өнцөг болохыг дүгнэж болно

$$ I_1 = (b-z) \overline{(a-z)} (a-c) \overline{(b-c)} $$

Хэрэв өнцөг $0^\circ$ эсвэл $180^\circ$ бол энэ нь $I_1$-ийн хуурмаг хэсэг $0$ гэсэн үг, эс бөгөөс бид $I_1$-ийн хуурмаг хэсгийн тэмдгийг шалгах замаар $z$ нь $abc$-ийн багтаах тойргийн дотор эсвэл гадна байгааг дүгнэж болно. Эерэг хуурмаг хэсэг эерэг өнцгүүдэд, сөрөг хуурмаг хэсэг сөрөг өнцгүүдэд харгалзана.

Гэвч тэдгээрийн аль нь $z$ тойргийн дотор эсвэл гадна байгааг илэрхийлэх вэ? Бидний аль хэдийн анзаарсанчлан $z$ тойргийн дотор байх нь ерөнхийдөө $\angle azb$-ийн хэмжээг ихэсгэх ба тойргийн гадна байх нь түүнийг багасгана. Иймд бидэнд дараах 4 тохиолдол байна:

$\angle bca > 0^\circ$, $c$ нь $ab$-ийн $z$-тэй ижил талд. Тэгвэл тойргийн доторх цэгүүдийн хувьд $\angle azb < 0^\circ$ ба $\angle azb + \angle bca < 0^\circ$.
$\angle bca < 0^\circ$, $c$ нь $ab$-ийн $z$-тэй ижил талд. Тэгвэл тойргийн доторх цэгүүдийн хувьд $\angle azb > 0^\circ$ ба $\angle azb + \angle bca > 0^\circ$.
$\angle bca > 0^\circ$, $c$ нь $ab$-ийн $z$-ээс эсрэг талд. Тэгвэл тойргийн доторх цэгүүдийн хувьд $\angle azb > 0^\circ$ ба $\angle azb + \angle bca > 180^\circ$.
$\angle bca < 0^\circ$, $c$ нь $ab$-ийн $z$-ээс эсрэг талд. Тэгвэл тойргийн доторх цэгүүдийн хувьд $\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$ нь оролт дахь координатын хамгийн том хэмжээ юм. Сайн тал нь оролт бүхэл тоо бол дээрх хоёр шалгалтыг бүрэн бүхэл тоогоор хийж болно.

Implementation¶

Now, to actually implement the check, we should first decide how to represent the MEC. As our criteria work with the points directly, a natural and efficient way to do this is to say that MEC is directly represented as a pair or triple of points that defines it:

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

Now, we can use std::visit to efficiently deal with both cases in accordance with criteria above:

/* 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;
}

Now, we can finally ensure that everything works by submitting the problem to the Library Checker: #308668.