Хагас хавтгайн огтлолцол¶

Энэ өгүүлэлд бид хагас хавтгайнуудын олонлогийн огтлолцлыг тооцоолох бодлогыг хэлэлцэнэ. Ийм огтлолцлыг гүдгэр муж/олон өнцөгт хэлбэрээр тохиромжтойгоор илэрхийлж болох ба түүний доторх цэг бүр бүх хагас хавтгайн дотор мөн байх бөгөөд бидний олох буюу байгуулахыг оролдож буй зүйл нь яг энэ олон өнцөгт юм. Бид бодлогын анхны ойлголтыг өгч, Sort-and-Incremental алгоритм гэж нэрлэгддэг $O(N \log N)$ аргыг тайлбарлаж, энэ аргын хэрэглээний зарим жишээг үзүүлнэ.

Уншигчид геометрийн үндсэн примитив ба үйлдлүүдтэй (цэг, вектор, шулуунуудын огтлолцол) танилцсан байхыг хатуу зөвлөж байна. Түүнчлэн Гүдгэр бүрхүүл эсвэл Гүдгэр бүрхүүлийн арга-ын талаарх мэдлэг энэ өгүүллийн ойлголтуудыг илүү сайн ойлгоход тусалж болох боловч тэдгээр нь урьдчилсан нөхцөл огт биш юм.

Анхны тодруулга ба тодорхойлолт¶

Бүхэл өгүүллийн турш бид зарим таамаглал гаргана (өөрөөр заагаагүй бол):

Бид $N$-г өгөгдсөн олонлог дахь хагас хавтгайнуудын тоо гэж тодорхойлно.
Бид шулуун ба хагас хавтгайг нэг цэг ба нэг вектороор илэрхийлнэ (өгөгдсөн шулуун дээр орших дурын цэг ба шулууны чиглүүлэгч вектор). Хагас хавтгайн хувьд бид хагас хавтгай бүр өөрийн чиглүүлэгч векторын зүүн талын мужийг зөвшөөрнө гэж үзнэ. Түүнчлэн бид хагас хавтгайн өнцгийг түүний чиглүүлэгч векторын туйлын өнцөг гэж тодорхойлно. Жишээг доорх зургаас үз.
Бид үүссэн огтлолцол үргэлж хязгаарлагдмал эсвэл хоосон байна гэж үзнэ. Хэрэв бид хязгаарлагдмал биш тохиолдлыг боловсруулах шаардлагатай бол хангалттай том хүрээлэх хайрцгийг тодорхойлох 4 хагас хавтгай зүгээр л нэмж болно.
Хялбар байдлын үүднээс бид өгөгдсөн олонлогт параллель хагас хавтгай байхгүй гэж үзнэ. Өгүүллийн төгсгөл рүү бид ийм тохиолдлуудтай хэрхэн ажиллахыг хэлэлцэнэ.

$y \geq 2x - 2$ хагас хавтгайг $PQ = Q - P = (1, 2)$ чиглүүлэгч вектортой $P = (1, 0)$ цэг хэлбэрээр илэрхийлж болно

Шууд хүчний арга - $O(N^3)$¶

Хамгийн энгийн бөгөөд илэрхий шийдийн нэг бол хагас хавтгайнуудын бүх хосын шулуунуудын огтлолцлын цэгийг тооцоолж, цэг бүрийн хувьд тэр нь бусад бүх хагас хавтгайн дотор байгаа эсэхийг шалгах явдал юм. $O(N^2)$ огтлолцлын цэг байх ба тэдгээр бүрийн хувьд бид $O(N)$ хагас хавтгай шалгах ёстой тул нийт time complexity нь $O(N^3)$ болно. Огтлолцлын бодит мужийг дараа нь жишээ нь бүх хагас хавтгайд багтсан огтлолцлын цэгүүдийн олонлог дээр Гүдгэр бүрхүүлийн алгоритм ашиглан сэргээж болно.

Энэ яагаад ажилладгийг харахад нэлээд амархан: үүссэн гүдгэр олон өнцөгтийн оройнууд бол хагас хавтгайн шулуунуудын бүх огтлолцлын цэгүүд бөгөөд эдгээр оройн тус бүр нь бүх хагас хавтгайн хэсэг байх нь илэрхий. Энэ аргын гол давуу тал нь хэрэв та зөвхөн огтлолцол хоосон эсэхийг шалгах шаардлагатай бол ойлгоход, санахад, шууд бичихэд амархан явдал юм. Гэвч энэ нь аймшигтай удаан бөгөөд ихэнх бодлогод тохиромжгүй тул бидэнд илүү хурдан зүйл хэрэгтэй.

Нэмэгдүүлэх арга - $O(N^2)$¶

Өөр нэг нэлээд энгийн арга бол хагас хавтгайнуудын огтлолцлыг нэг нэгээр нь нэмэгдүүлэн байгуулах явдал юм. Энэ арга нь үндсэндээ гүдгэр олон өнцөгтийг $N$ удаа шулуунаар зүсэж, алхам бүрд илүүдэл хагас хавтгайнуудыг хасахтай эквивалент юм. Үүний тулд бид гүдгэр олон өнцөгтийг хэрчмүүдийн жагсаалт хэлбэрээр илэрхийлж болох ба түүнийг хагас хавтгайгаар зүсэхийн тулд бид зүгээр л хэрчмүүд ба хагас хавтгайн шулууны огтлолцлын цэгүүдийг олоод (хэрэв шулуун олон өнцөгтийг зохих ёсоор огтолж байвал ердөө хоёр огтлолцлын цэг байна), тэдгээрийн хоорондох бүх хэрчмийг хагас хавтгайд харгалзах шинэ хэрчмээр солино. Ийм үйл ажиллагааг шугаман хугацаанд хэрэгжүүлэх боломжтой тул бид зүгээр л том хүрээлэх хайрцгаас эхлээд хагас хавтгай бүрээр түүнийг зүсэж, нийт $O(N^2)$ time complexity авч болно.

Энэ арга бол зөв чиглэл рүү хийсэн том алхам боловч алхам бүрд $O(N)$ хагас хавтгайг тойрох шаардлагатай нь үрэлгэн санагдана. Дараа нь бид зарим ухаалаг ажиглалт хийснээр энэ нэмэгдүүлэх аргын ард байгаа санааг $O(N \log N)$ алгоритм үүсгэхэд дахин ашиглаж болохыг үзнэ.

Sort-and-Incremental алгоритм - $O(N \log N)$¶

Энэ алгоритмын бидний олж чадсан анхны зохих ёсоор баримтжуулсан эх сурвалж бол Зэюань Жугийн Хятадын шигшээ багийн сонгон шалгаруулах тэмцээнд зориулсан 2006 оны New Algorithm for Half-plane Intersection and its Practical Value нэртэй дипломын ажил байв. Бидний дараа тайлбарлах арга нь яг энэ алгоритм дээр суурилах боловч огтлолцлын доод ба дээд хагасын хувьд хоёр тусдаа огтлолцол тооцоолохын оронд бид бүгдийг нэг дамжилтаар deque (хоёр талтай дараалал) ашиглан нэг дор байгуулна.

Алгоритм өөрөө нэрнээсээ мэдэгдэж болохын адил хагас хавтгайнуудын огтлолцлоос үүсэх муж нь гүдгэр байдаг гэсэн баримтыг ашигладаг ба ингэснээр тэр нь өнцгүүдээрээ эрэмбэлэгдсэн дарааллаар хагас хавтгайнуудын зарим хэрчмээс бүрдэнэ. Энэ нь нэн чухал ажиглалтад хүргэнэ: хэрэв бид хагас хавтгайнуудыг өнцгөөр эрэмбэлэгдсэн дарааллаар нь (огтлолцлын эцсийн, үүссэн дүрсэд гарч ирэхийн адил) нэмэгдүүлэн огтлолцуулж, хоёр талтай дараалалд хадгалбал бид зөвхөн deque-ийн урд ба хойд талаас хагас хавтгайнуудыг хасах шаардлагатай болно.

Энэ баримтыг илүү сайн төсөөлөхийн тулд бид өнцгөөр эрэмбэлэгдсэн хагас хавтгайнуудын олонлог дээр өмнө тайлбарласан нэмэгдүүлэх аргыг гүйцэтгэж байна гэж үзье (энэ тохиолдолд бид тэдгээрийг $-\pi$-ээс $\pi$ хүртэл эрэмбэлсэн гэж үзнэ), мөн бид дурын $k$-р алхмыг эхлэх гэж байна гэж үзье. Энэ нь бид эхний $k-1$ хагас хавтгайн огтлолцлыг аль хэдийн байгуулсан гэсэн үг. Одоо хагас хавтгайнууд өнцгөөр эрэмбэлэгдсэн тул $k$-р хагас хавтгай ямар ч байсан тэр нь $(K-1)$-р хагас хавтгайтай гүдгэр эргэлт үүсгэнэ гэдэгт бид итгэлтэй байж болно. Тийм учраас хэдэн зүйл тохиолдож болно:

Огтлолцлын хойд талд байгаа зарим (магадгүй нэг ч биш) хагас хавтгай илүүдэл болж болно. Энэ тохиолдолд бид одоо хэрэггүй болсон эдгээр хагас хавтгайг deque-ийн хойд талаас хасах хэрэгтэй.
Урд талд байгаа зарим (магадгүй нэг ч биш) хагас хавтгай илүүдэл болж болно. 1-р тохиолдолтой адилаар бид тэдгээрийг зүгээр л deque-ийн урд талаас хасна.
Огтлолцол хоосон болж болно (1 ба/эсвэл 2-р тохиолдлыг боловсруулсны дараа). Энэ тохиолдолд бид зүгээр л огтлолцол хоосон гэж мэдээлээд алгоритмыг зогсооно.

Хэрэв хагас хавтгай огтлолцолд юу ч оруулахгүй бол бид түүнийг "илүүдэл" гэж хэлнэ. Ийм хагас хавтгайг хасч болох ба үүссэн огтлолцол огт өөрчлөгдөхгүй.

Энд зурган тайлбартай жижиг жишээ байна:

$H = \{ A, B, C, D, E \}$ нь огтлолцолд одоогоор байгаа хагас хавтгайнуудын олонлог байг. Түүнчлэн $P = \{ p, q, r, s \}$ нь H дэх зэргэлдээ хагас хавтгайнуудын огтлолцлын цэгүүдийн олонлог байг. Одоо бид доорх зурган тайлбарт үзүүлсэнчлэн үүнийг $F$ хагас хавтгайтай огтлолцуулахыг хүсэж байна гэж үзье:

$F$ хагас хавтгай огтлолцолд $A$ ба $E$-г илүүдэл болгож байгааг анхаарна уу. Тиймээс бид $A$ ба $E$-г огтлолцлын урд ба хойд талаас харгалзан хасаад төгсгөлд нь $F$-г нэмнэ. Эцэст нь бид $P = \{ q, r, t, u \}$-тэй $H = \{ B, C, D, F\}$ шинэ огтлолцлыг авна.

Энэ бүхнийг харгалзан бид алгоритмыг үнэхээр хэрэгжүүлэхэд хэрэгтэй бараг бүх зүйлтэй болсон боловч бид зарим тусгай тохиолдлын талаар ярих хэрэгтэй хэвээр байна. Өгүүллийн эхэнд бид огтлолцол хязгаарлагдмал биш байж болох тохиолдлыг зохицуулахын тулд хүрээлэх хайрцаг нэмнэ гэж хэлсэн тул бидний үнэндээ боловсруулах шаардлагатай цорын ганц төвөгтэй тохиолдол бол параллель хагас хавтгайнууд юм. Бидэнд хоёр дэд тохиолдол байж болно: хоёр хагас хавтгай ижил чиглэлтэй эсвэл эсрэг чиглэлтэй параллель байж болно. Энэ тохиолдлыг тусад нь боловсруулах шаардлагатай шалтгаан нь бид хагас хавтгай илүүдэл эсэхийг шалгахын тулд хагас хавтгайн шулуунуудын огтлолцлын цэгүүдийг тооцоолох шаардлагатай болох ба параллель хоёр шулуун огтлолцлын цэггүй тул тэдгээртэй ажиллах тусгай арга хэрэгтэй болно.

Эсрэг чиглэлтэй параллель хагас хавтгайнуудын тохиолдолд: Бид хязгаарлагдмал биш тохиолдолтой ажиллахын тулд хүрээлэх хайрцаг нэмж байгаа тул энэ нь эрэмбэлсний дараа эсрэг чиглэлтэй зэргэлдээ параллель хоёр хагас хавтгайтай болох тохиолдлыг ч зохицуулна гэдгийг анхаарна уу, учир нь эдгээр хоёрын хооронд хүрээлэх хайрцгийн хагас хавтгайнуудын дор хаяж нэг нь байх ёстой (тэдгээр өнцгөөр эрэмбэлэгдсэн гэдгийг санаарай).

Гэвч deque-ийн хойд талаас зарим хагас хавтгайг хассаны дараа эсрэг чиглэлтэй параллель хоёр хагас хавтгай хамт үлдэх боломжтой. Энэ тохиолдол зөвхөн эдгээр хоёр хагас хавтгай хоосон огтлолцол үүсгэх үед л тодруулбал тохиолддог, учир нь энэ сүүлчийн хагас хавтгай deque-ээс бүх зүйлийг хасахад хүргэнэ. Энэ асуудлаас зайлсхийхийн тулд бид параллель хагас хавтгайнуудыг гараар шалгах ёстой бөгөөд хэрэв тэдгээр эсрэг чиглэлтэй бол бид зүгээр л алгоритмыг шууд зогсоож, хоосон огтлолцол буцаана.

Ингэснээр бидний үнэндээ боловсруулах шаардлагатай цорын ганц тохиолдол бол ижил өнцөгтэй хэд хэдэн хагас хавтгайтай байх явдал бөгөөд энэ тохиолдлыг боловсруулахад нэлээд амархан болох нь тогтоогддог: бид зөвхөн хамгийн зүүн талын хагас хавтгайг үлдээж, бусдыг нь устгахад л хангалттай, учир нь тэдгээр ямар ч байсан бүрэн илүүдэл байх болно. Дүгнэвэл бүрэн алгоритм ойролцоогоор дараах байдалтай байна:

Бид хагас хавтгайнуудын олонлогийг өнцгөөр эрэмбэлэхээс эхэлнэ, энэ нь $O(N \log N)$ хугацаа авна.
Бид хагас хавтгайнуудын олонлогийг тойрч, тус бүрийн хувьд нэмэгдүүлэх үйл ажиллагааг гүйцэтгэн, шаардлагатай бол хоёр талтай дарааллын урд ба хойд талаас хасна. Хагас хавтгай бүр зөвхөн нэг удаа нэмэгдэж эсвэл хасагдаж чадах тул энэ нь нийтдээ шугаман хугацаа авна.
Эцэст нь огтлолцлоос үүсэх гүдгэр олон өнцөгтийг үйл ажиллагааны төгсгөлд deque дэх зэргэлдээ хагас хавтгайнуудын огтлолцлын цэгүүдийг тооцоолох замаар зүгээр л авч болно. Энэ нь мөн шугаман хугацаа авна. Мөн 2-р алхмын явцад ийм цэгүүдийг хадгалж, энэ алхмыг бүрэн алгасах боломжтой боловч бид тэдгээрийг шууд тооцоолох нь (хэрэгжүүлэлтийн хувьд) арай илүү хялбар гэж үзэж байна.

Нийтдээ бид $O(N \log N)$ time complexity-д хүрлээ. Эрэмбэлэлт нь тодорхой хүзүү тул хагас хавтгайнуудыг өнцгөөр нь урьдчилан эрэмбэлж өгсөн тусгай тохиолдолд алгоритмыг шугаман хугацаанд ажиллуулж болно (ийм тохиолдлын жишээ нь гүдгэр олон өнцөгтийг тодорхойлох хагас хавтгайнуудыг авах явдал юм).

Direct implementation¶

Here is a sample, direct implementation of the algorithm, with comments explaining most parts:

Simple point/vector and half-plane structs:

// Redefine epsilon and infinity as necessary. Be mindful of precision errors.
const long double eps = 1e-9, inf = 1e9; 

// Basic point/vector struct.
struct Point { 

    long double x, y;
    explicit Point(long double x = 0, long double y = 0) : x(x), y(y) {}

    // Addition, subtraction, multiply by constant, dot product, cross product.

    friend Point operator + (const Point& p, const Point& q) {
        return Point(p.x + q.x, p.y + q.y); 
    }

    friend Point operator - (const Point& p, const Point& q) { 
        return Point(p.x - q.x, p.y - q.y); 
    }

    friend Point operator * (const Point& p, const long double& k) { 
        return Point(p.x * k, p.y * k); 
    } 

    friend long double dot(const Point& p, const Point& q) {
        return p.x * q.x + p.y * q.y;
    }

    friend long double cross(const Point& p, const Point& q) { 
        return p.x * q.y - p.y * q.x; 
    }
};

// Basic half-plane struct.
struct Halfplane { 

    // 'p' is a passing point of the line and 'pq' is the direction vector of the line.
    Point p, pq; 
    long double angle;

    Halfplane() {}
    Halfplane(const Point& a, const Point& b) : p(a), pq(b - a) {
        angle = atan2l(pq.y, pq.x);    
    }

    // Check if point 'r' is outside this half-plane. 
    // Every half-plane allows the region to the LEFT of its line.
    bool out(const Point& r) { 
        return cross(pq, r - p) < -eps; 
    }

    // Comparator for sorting. 
    bool operator < (const Halfplane& e) const { 
        return angle < e.angle;
    } 

    // Intersection point of the lines of two half-planes. It is assumed they're never parallel.
    friend Point inter(const Halfplane& s, const Halfplane& t) {
        long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq);
        return s.p + (s.pq * alpha);
    }
};

Algorithm:

// Actual algorithm
vector<Point> hp_intersect(vector<Halfplane>& H) { 

    Point box[4] = {  // Bounding box in CCW order
        Point(inf, inf), 
        Point(-inf, inf), 
        Point(-inf, -inf), 
        Point(inf, -inf) 
    };

    for(int i = 0; i<4; i++) { // Add bounding box half-planes.
        Halfplane aux(box[i], box[(i+1) % 4]);
        H.push_back(aux);
    }

    // Sort by angle and start algorithm
    sort(H.begin(), H.end());
    deque<Halfplane> dq;
    int len = 0;
    for(int i = 0; i < int(H.size()); i++) {

        // Remove from the back of the deque while last half-plane is redundant
        while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) {
            dq.pop_back();
            --len;
        }

        // Remove from the front of the deque while first half-plane is redundant
        while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
            dq.pop_front();
            --len;
        }

        // Special case check: Parallel half-planes
        if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) {
            // Opposite parallel half-planes that ended up checked against each other.
            if (dot(H[i].pq, dq[len-1].pq) < 0.0)
                return vector<Point>();

            // Same direction half-plane: keep only the leftmost half-plane.
            if (H[i].out(dq[len-1].p)) {
                dq.pop_back();
                --len;
            }
            else continue;
        }

        // Add new half-plane
        dq.push_back(H[i]);
        ++len;
    }

    // Final cleanup: Check half-planes at the front against the back and vice-versa
    while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) {
        dq.pop_back();
        --len;
    }

    while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) {
        dq.pop_front();
        --len;
    }

    // Report empty intersection if necessary
    if (len < 3) return vector<Point>();

    // Reconstruct the convex polygon from the remaining half-planes.
    vector<Point> ret(len);
    for(int i = 0; i+1 < len; i++) {
        ret[i] = inter(dq[i], dq[i+1]);
    }
    ret.back() = inter(dq[len-1], dq[0]);
    return ret;
}

Implementation discussion¶

A special thing to note is that, in case there multiple half-planes that intersect at the same point, then this algorithm could return repeated adjacent points in the final polygon. However, this should not have any impact on judging correctly whether the intersection is empty or not, and it does not affect the polygon area at all either. You may want to remove these duplicates depending on what tasks you need to do after. You can do this very easily with std::unique. We want to keep the repeat points during the execution of the algorithm so that the intersections with area equal to zero can be computed correctly (for example, intersections that consist of a single point, line or line-segment). I encourage the reader to test some small hand-made cases where the intersection results in a single point or line.

One more thing that should be talked about is what to do if we are given half-planes in the form of a linear constraint (for example, $ax + by + c \leq 0$). In such case, there are two options. You can either implement the algorithm with the corresponding modifications to work with such representation (essentially create your own half-plane struct, should be fairly straightforward if you're familiar with the convex hull trick), or you can transform the lines into the representation we used in this article by taking any 2 points of each line. In general, it is recommended to work with the representation that you're given in the problem to avoid additional precision issues.

Бодлого, даалгавар ба хэрэглээ¶

Хагас хавтгайн огтлолцлоор бодож болох олон бодлогыг үүнгүйгээр ч бодож болох боловч (ихэвчлэн) илүү төвөгтэй эсвэл ховор аргаар бодно. Ерөнхийдөө хагас хавтгайн огтлолцол нь олон өнцөгт (ихэвчлэн гүдгэр), хавтгай дахь харагдац ба хоёр хэмжээст шугаман программчлалтай холбоотой бодлоготой ажиллах үед гарч ирж болно. Энэ аргаар бодож болох зарим жишээ даалгавар энд байна:

Гүдгэр олон өнцөгтүүдийн огтлолцол¶

Хагас хавтгайн огтлолцлын сонгодог хэрэглээний нэг: $N$ олон өнцөгт өгөгдсөн үед бүх олон өнцөгтийн дотор багтах мужийг тооцоол.

Хагас хавтгайнуудын олонлогийн огтлолцол нь гүдгэр олон өнцөгт байдаг тул бид гүдгэр олон өнцөгтийг мөн хагас хавтгайнуудын олонлог хэлбэрээр илэрхийлж болно (олон өнцөгтийн ирмэг бүр нь хагас хавтгайн хэрчим юм). Олон өнцөгт бүрийн хувьд эдгээр хагас хавтгайг үүсгээд бүхэл олонлогийн огтлолцлыг тооцоол. Нийт time complexity нь $O(S \log S)$, энд S нь бүх олон өнцөгтийн талуудын нийт тоо юм. Бодлогыг онолын хувьд $N$ ширхэг хагас хавтгайн олонлогийг овоолго ашиглан нийлүүлж, дараа нь эрэмбэлэх алхамгүйгээр алгоритмыг ажиллуулах замаар $O(S \log N)$-д ч бодож болно, гэвч ийм шийд шууд эрэмбэлэхээс хамаагүй муу тогтмол үржүүлэгчтэй бөгөөд зөвхөн маш бага $N$-ийн хувьд бага зэргийн хурдны ашиг өгнө.

Хавтгай дахь харагдац¶

"Хавтгай дахь ямар нэг цэг(үүд)-ээс зарим хэрчим харагдаж байгаа эсэхийг тодорхойл" гэсэн шугамын дагуух зүйл шаарддаг бодлогуудыг ихэвчлэн хагас хавтгайн огтлолцлын бодлого хэлбэрээр томьёолж болно. Жишээ нь дараах даалгаврыг ав: Ямар нэг энгийн олон өнцөгт (заавал гүдгэр байх албагүй) өгөгдсөн үед олон өнцөгтийн бүхэл заагийг ажиглаж болох цэг олон өнцөгтийн дотор байгаа эсэхийг тодорхойл. Үүнийг мөн олон өнцөгтийн цөмийг олох гэж нэрлэдэг ба олон өнцөгтийн ирмэг бүрийг хагас хавтгай болгон аваад түүний огтлолцлыг тооцоолох замаар энгийн хагас хавтгайн огтлолцлоор бодож болно.

Энд Артем Васильевийн Бразилийн ICPC зуны сургуулийн лекцүүдийн нэгэнд танилцуулсан холбогдох, илүү сонирхолтой бодлого байна: Хавтгай дээр $p_1, p_2\ \dots \ p_n$ цэгүүдийн $p$ олонлог өгөгдсөн үед та $p$-ийн бүх цэгийг индексийнх нь өсөх дарааллаар зүүнээс баруун тийш харж чадах $q$ цэг байгаа эсэхийг тодорхойл.

Ийм бодлогыг $p_j$-ийн зүүн талд байгаа ямар нэг $p_i$ цэгийг харж чадах нь $p_i$-ээс $p_j$ хүртэлх хэрчмийн баруун талыг харж чадахтай (эсвэл үүнтэй эквивалентээр $p_j$-ээс $p_i$ хүртэлх хэрчмийн зүүн талыг харж чадахтай) ижил болохыг анзаарах замаар бодож болно. Үүнийг харгалзан бид $p_i p_{i+1}$ хэрчим бүрийн хувьд (эсвэл таны сонгосон чиглэлээс хамааран $p_{i+1} p_i$) хагас хавтгайг зүгээр л үүсгээд бүхэл олонлогийн огтлолцол хоосон эсэхийг шалгаж болно.

Хоёртын хайлттай хагас хавтгайн огтлолцол¶

Өөр нэг түгээмэл хэрэглээ бол хагас хавтгайн огтлолцлыг хоёртын хайлтын үйл ажиллагааны предикатыг шалгах хэрэгсэл болгон ашиглах явдал юм. Энд өмнө дурдсан ижил лекцэд Артем Васильевийн мөн танилцуулсан ийм бодлогын жишээ байна: Гүдгэр олон өнцөгт $P$ өгөгдсөн үед түүний дотор багтааж болох хамгийн том тойргийг ол.

Ямар нэг битүү хэлбэрийн шийд, төвөгтэй томьёо эсвэл ойлгомжгүй алгоритмын шийд хайхын оронд хариулт дээр хоёртын хайлт хийхийг оролдъё. Ямар нэг тогтмол $r$-ийн хувьд $r$ радиустай тойргийг $P$-ийн дотор зөвхөн $P$-ийн заагийн бүх цэг хүртэл $r$-ээс их буюу тэнцүү зайтай цэг $P$-ийн дотор оршиж байвал багтааж болохыг анхаарна уу. Энэ нөхцөлийг олон өнцөгтийг дотогшоо $r$ зайгаар "агшаах" ба олон өнцөгт degenerate case биш хэвээр байгааг (эсвэл өөрөө цэг/хэрчим болохыг) шалгах замаар шалгаж болно. Ийм үйл ажиллагааг олон өнцөгтийн талуудын хагас хавтгайг цагийн зүүний эсрэг дарааллаар аваад тус бүрийг нь тэдгээрийн зөвшөөрөх мужийн чиглэлд (өөрөөр хэлбэл хагас хавтгайн чиглүүлэгч вектортой ортогональ) $r$ зайгаар шилжүүлж, огтлолцол хоосон биш эсэхийг шалгах замаар загварчилж болно.

Хэрэв бид $r$ радиустай тойрог багтааж чадвал $r$-ээс бага радиустай өөр дурын тойргийг ч багтааж чадах нь тодорхой. Тиймээс бид $r$ радиус дээр хоёртын хайлт хийж, алхам бүрийг хагас хавтгайн огтлолцол ашиглан шалгаж болно. Мөн гүдгэр олон өнцөгтийн хагас хавтгайнууд аль хэдийн өнцгөөр эрэмбэлэгдсэн байдаг тул алгоритмд эрэмбэлэх алхмыг алгасаж болохыг анхаарна уу. Ингэснээр бид нийт $O(NK)$ time complexity авна, энд $N$ нь олон өнцөгтийн оройн тоо, $K$ нь хоёртын хайлтын итерацын тоо (бодит утга нь боломжит хариултуудын муж ба хүссэн нарийвчлалаас хамаарна).

Хоёр хэмжээст шугаман программчлал¶

Хагас хавтгайн огтлолцлын өөр нэг хэрэглээ бол хоёр хувьсагчтай шугаман программчлал юм. Хоёр хувьсагчийн бүх шугаман хязгаарлалтыг $Ax + By + C \leq 0$ хэлбэрээр илэрхийлж болно (тэнцэтгэл бишийн харьцуулагч өөр байж болно). Эдгээр нь зүгээр л хагас хавтгайнууд болох нь тодорхой тул шугаман хязгаарлалтуудын олонлогийн хувьд боломжит шийд оршин байгаа эсэхийг шалгахыг хагас хавтгайн огтлолцлоор хийж болно. Түүнчлэн өгөгдсөн шугаман хязгаарлалтуудын олонлогийн хувьд боломжит шийдүүдийн мужийг (өөрөөр хэлбэл хагас хавтгайнуудын огтлолцлыг) тооцоолж, дараа нь хязгаарлалтуудад захирагдах ямар нэг шугаман функц $f(x, y)$-г максимумчлах/минимумчлах олон асуулгад хоёртын хайлт ашиглан асуулга тутамд $O(\log N)$-д хариулах боломжтой (гүдгэр бүрхүүлийн аргатай маш төстэй).

Шугаман хязгаарлалтуудын олонлог боломжит шийдтэй эсэхийг шалгаж, өгөгдсөн хязгаарлалтуудад захирагдах ямар нэг шугаман функцийг максимумчлах/минимумчлах чадвартай нэлээд энгийн санамсаргүй алгоритм ч мөн байдгийг дурдах нь зүйтэй. Энэ санамсаргүй алгоритмыг мөн Артем Васильев өмнө дурдсан лекцэд сайхан тайлбарласан. Уншигч сонирхож байвал энд түүний талаарх зарим нэмэлт эх сурвалж байна: CG - Lecture 4, parts 4 and 5 ба Petr Mitrichev's blog (доорх дасгал бодлогуудын жагсаалт дахь хамгийн хэцүү бодлогын шийдийг агуулсан).

Дасгал бодлогууд¶

Сонгодог бодлогууд, шууд хэрэглээ¶

Илүү хэцүү бодлогууд¶

Нэмэлт бодлогууд¶

40th Petrozavodsk Programming Camp, Winter 2021 - Day 1: Jagiellonian U Contest, Grand Prix of Krakow - Problem B: (Almost) Fair Cake-Cutting. At the time of writing the article, this problem was private and only accessible by participants of the Programming Camp.

Эх сурвалж, ном зүй ба бусад эх үүсвэр¶

Үндсэн эх сурвалж¶

New Algorithm for Half-plane Intersection and its Practical Value. Original paper of the algorithm.
Artem Vasilyev's Brazilian ICPC Summer School 2020 lecture. Amazing lecture on half-plane intersection. Also covers other geometry topics.