Манхэттэний зай¶

Тодорхойлолт¶

Хавтгай дээрх $p$ ба $q$ цэгүүдийн хувьд бид тэдгээрийн хоорондох зайг $x$ ба $y$ координатуудынх нь ялгаваруудын нийлбэр гэж тодорхойлж болно:

$$d(p,q) = |x_p - x_q| + |y_p - y_q|$$

Ийнхүү тодорхойлсон зай нь Манхэттэний (таксины) геометр гэж нэрлэгддэг зүйлд харгалзана, үүнд цэгүүдийг Манхэттэн шиг сайн төлөвлөсөн хотын уулзваруудад авч үзэх ба доорх зурган дээр үзүүлсэнчлэн та зөвхөн гудамжаар хэвтээ эсвэл босоо чиглэлд хөдөлж чадна:

Энэ зураг нэг хар цэгээс нөгөө рүү очих хамгийн богино замуудын заримыг харуулж байгаа ба тэдгээр бүгд $12$ урттай.

Энэ зайтай холбоотой хийж болох сонирхолтой заль мэх, алгоритмууд байдаг бөгөөд бид тэдгээрийн заримыг энд үзүүлнэ.

Манхэттэний зайгаар хамгийн хол цэгүүдийн хос¶

$n$ ширхэг $P$ цэг өгөгдсөн үед бид хамгийн хол зайтай $p,q$ цэгүүдийн хосыг олохыг, өөрөөр хэлбэл $|x_p - x_q| + |y_p - y_q|$-г максимумчлахыг хүсэж байна.

Эхлээд нэг хэмжээст орон зайд бодъё, тэгэхээр $y=0$. Гол ажиглалт бол $|x_p - x_q|$ нь $x_p - x_q$ эсвэл $-x_p + x_q$-тэй тэнцүү эсэхийг бид шууд хүчээр оролдож болно, учир нь хэрэв бид үнэмлэхүй утгын "тэмдгийг алдвал" зөвхөн бага утга авах тул энэ нь хариултад нөлөөлж чадахгүй. Илүү албан ёсоор дараах нь биелнэ:

$$|x_p - x_q| = \max(x_p - x_q, -x_p + x_q)$$

Тэгэхээр жишээ нь бид $x_p$ нэмэх тэмдэгтэй байх $p$-г авахыг оролдож болох ба тэгвэл $q$ хасах тэмдэгтэй байх ёстой. Ингэснээр бид дараахыг олохыг хүсэж байна:

$$\max\limits_{p, q \in P}(x_p + (-x_q)) = \max\limits_{p \in P}(x_p) + \max\limits_{q \in P}( - x_q ).$$

Бид энэ санааг 2 (эсвэл түүнээс олон!) хэмжээст рүү өргөтгөж болохыг анхаарна уу. $d$ хэмжээсийн хувьд бид тэмдгүүдийн $2^d$ боломжит утгыг шууд хүчээр оролдох ёстой. Жишээ нь хэрэв бид $2$ хэмжээст орон зайд байгаа бөгөөд $p$ хоёулаа нэмэх тэмдэгтэй гэж шууд хүчээр оролдвол бид дараахыг олохыг хүснэ:

$$\max\limits_{p, q \in P} [(x_p + (-x_q)) + (y_p + (-y_q))] = \max\limits_{p \in P}(x_p + y_p) + \max\limits_{q \in P}(-x_q - y_q).$$

Бид $p$ ба $q$-г хамааралгүй болгосон тул одоо илэрхийллийг максимумчлах $p$ ба $q$-г олоход амархан.

Доорх код үүнийг $d$ хэмжээст рүү ерөнхийлөх ба $O(n \cdot 2^d \cdot d)$-д ажиллана.

long long ans = 0;
for (int msk = 0; msk < (1 << d); msk++) {
    long long mx = LLONG_MIN, mn = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        long long cur = 0;
        for (int j = 0; j < d; j++) {
            if (msk & (1 << j)) cur += p[i][j];
            else cur -= p[i][j];
        }
        mx = max(mx, cur);
        mn = min(mn, cur);
    }
    ans = max(ans, mx - mn);
}

Цэгүүдийг эргүүлэх ба Чебышевийн зай¶

Бүх $m, n \in \mathbb{R}$-ийн хувьд дараах нь сайн мэдэгддэг,

$$|m| + |n| = \text{max}(|m + n|, |m - n|).$$

Үүнийг батлахын тулд бид зөвхөн $m$ ба $n$-ийн тэмдгүүдийг шинжлэх хэрэгтэй. Үүнийг дасгал болгон үлдээв.

Бид энэ тэгшитгэлийг Манхэттэний зайн томьёонд хэрэглэн дараахыг олж болно

$$d((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2| = \text{max}(|(x_1 + y_1) - (x_2 + y_2)|, |(y_1 - x_1) - (y_2 - x_2)|).$$

Өмнөх тэгшитгэл дэх сүүлчийн илэрхийлэл нь $(x_1 + y_1, y_1 - x_1)$ ба $(x_2 + y_2, y_2 - x_2)$ цэгүүдийн Чебышевийн зай юм. Энэ нь дараах хувиргалтыг хэрэглэсний дараа

$$\alpha : (x, y) \to (x + y, y - x),$$

$p$ ба $q$ цэгүүдийн хоорондох Манхэттэний зай нь $\alpha(p)$ ба $\alpha(q)$-ийн хоорондох Чебышевийн зай болж хувирна гэсэн үг юм.

Мөн бид $\alpha$ нь $(0, 0)$ төвтэй, цагийн зүүний дагуу чиглэлд $45^{\circ}$ эргэлтийн өнцөгтэй, $\sqrt{2}$-оор томсгосон спираль төстэй хувиргалт (хавтгайг эргүүлээд $O$ төвийн хувьд томсгох) болохыг ойлгож болно.

Хувиргалтыг төсөөлөхөд туслах зураг энд байна:

Манхэттэний хамгийн бага тэлэх мод¶

Манхэттэний MST бодлого нь хавтгай дээр цэгүүд өгөгдсөн үед бүх цэгийг холбох ба жингүүдийн нийт нийлбэр нь хамгийн бага байх ирмэгүүдийг олох явдал юм. Хоёр цэгийг холбох ирмэгийн жин нь тэдгээрийн Манхэттэний зай юм. Хялбар байдлын үүднээс бид бүх цэг өөр өөр байрлалтай гэж үзнэ. Энд бид доорх зурган дээр үзүүлсэнчлэн цэг бүрийн хувьд октант бүр дэх хамгийн ойрын хөршийг нь олох замаар MST-г $O(n \log{n})$-д олох аргыг үзүүлнэ. Энэ нь бидэнд $O(n)$ нэр дэвшигч ирмэг өгөх ба доор үзүүлэхийн адил тэдгээр MST-г агуулах нь баталгаатай болно. Эцсийн алхам нь ямар нэг стандарт MST, жишээ нь огтлолцолгүй олонлогийн нэгдэл ашигласан Крускалын алгоритм-ыг ашиглах явдал юм.

*S цэгийн хувьд 8 октант*

Энд үзүүлсэн алгоритмыг анх H. Zhou, N. Shenoy, W. Nichollos (2002) нарын өгүүлэлд танилцуулсан. Мөн J. Stolfi-ийн хуваа ба ялагтун арга барилыг ашигладаг өөр нэг мэдэгдэж буй алгоритм байдаг бөгөөд энэ нь мөн маш сонирхолтой ба зөвхөн октант бүр дэх хамгийн ойрын хөршийг олох аргаараа ялгаатай. Тэдгээр хоёул ижил complexity-тэй боловч энд үзүүлсэн нь хэрэгжүүлэхэд илүү хялбар бөгөөд илүү бага тогтмол үржүүлэгчтэй.

Эхлээд яагаад октант бүр дэх зөвхөн хамгийн ойрын хөршийг авч үзэхэд хангалттай болохыг ойлгоцгооё. Санаа нь $s$ цэг ба нэг октант дахь өөр дурын хоёр $p$, $q$ цэгийн хувьд $d(p, q) < \max(d(s, p), d(s, q))$ болохыг харуулах явдал юм. Энэ нь чухал, учир нь хэрэв $s$ нь $p$ ба $q$-тай хоёуланд нь холбогдсон MST байсан бол бид эдгээр ирмэгийн нэгийг устгаж, $(p,q)$ ирмэгийг нэмж болох ба энэ нь нийт өртгийг бууруулах болохыг харуулж байна. Үүнийг батлахын тулд бид ерөнхий чанараа алдалгүйгээр $p$ ба $q$ нь $x_s \leq x$ ба $x_s - y_s > x - y$-ээр тодорхойлогддог $R_1$ октантад байна гэж үзээд дараа нь тохиолдлуудыг шинжилнэ. Доорх зураг яагаад энэ нь үнэн болох талаар зарим ойлголт өгнө.

*Зөнгөөрөө бол октантын хязгаарлалт нь $p$ ба $q$ хоёул бие биенээсээ илүү $s$-д ойр байхыг боломжгүй болгодог*

Тиймээс гол асуулт бол $n$ цэг бүрийн хувьд октант бүр дэх хамгийн ойрын хөршийг хэрхэн олох явдал юм.

Октант бүр дэх хамгийн ойрын хөршийг O(n log n)-д олох¶

Хялбар байдлын үүднээс бид NNE октант (дээрх зурган дээрх $R_1$) дээр анхаарлаа хандуулна. Бусад бүх чиглэлийг оролтыг эргүүлэх замаар ижил алгоритмаар олж болно.

Бид шүүрдэх шулууны арга барилыг ашиглана. Бид цэгүүдийг баруун урдаас зүүн хойш, өөрөөр хэлбэл $x + y$-ийн буурахгүй дарааллаар боловсруулна. Мөн бид хамгийн ойрын хөршөө хараахан олоогүй байгаа цэгүүдийн олонлогийг хөтлөх ба үүнийг "идэвхтэй олонлог" гэж нэрлэнэ. Алгоритмыг төсөөлөхөд туслах зургуудыг доор нэмэв.

*Сумтай хараар шүүрдэх шулууны чиглэлийг харж болно. Энэ шулуунаас доош байгаа бүх цэг идэвхтэй олонлогт байх ба дээш байгаа цэгүүд хараахан боловсруулагдаагүй байна. Ногооноор боловсруулагдсан цэгийн октантад байгаа цэгүүдийг харж байна. Улаанаар хайж буй октантад байхгүй цэгүүдийг харууллаа.*

*Энэ зурган дээр бид $p$ цэгийг боловсруулсны дараах идэвхтэй олонлогийг харж байна. Өмнөх зургийн $2$ ногоон цэг өөрсдийн хойд-хойд-зүүн октантад $p$-г агуулж байсан ба тэдгээр хамгийн ойрын хөршөө аль хэдийн олсон тул идэвхтэй олонлогт байхаа больсныг анхаарна уу.*

Бид шинэ $p$ цэг нэмэхэд түүнийг өөрийн октантдаа агуулах $s$ цэг бүрийн хувьд бид $p$-г хамгийн ойрын хөрш гэж аюулгүйгээр оноож болно. Энэ нь үнэн, учир нь $p$ хойд-хойд-зүүн октантад байгаа тул тэдгээрийн зай $d(p,s) = |x_p - x_s| + |y_p - y_s| = (x_p + y_p) - (x_s + y_s)$ байна. Эрэмбэлэх алхмын улмаас дараагийн бүх цэг $x + y$-ийн бага утгатай байхгүй тул $p$ бага зайтай байх нь баталгаатай. Дараа нь бид ийм бүх цэгийг идэвхтэй олонлогоос хасаж, эцэст нь $p$-г идэвхтэй олонлогт нэмж болно.

Дараагийн асуулт бол аль $s$ цэгүүд $p$-г хойд-хойд-зүүн октантдаа агуулж байгааг хэрхэн үр ашигтай олох явдал юм. Өөрөөр хэлбэл аль $s$ цэгүүд дараахыг хангах вэ:

$x_s \leq x_p$
$x_p - y_p < x_s - y_s$

Идэвхтэй олонлог дахь ямар ч цэг нөгөөгийнхөө $R_1$ мужид байдаггүй тул идэвхтэй олонлог дахь $q_1$ ба $q_2$ хоёр цэгийн хувьд $x_{q_1} \neq x_{q_2}$ байх ба тэдгээрийн эрэмбэ нь $x_{q_1} < x_{q_2} \implies x_{q_1} - y_{q_1} \leq x_{q_2} - y_{q_2}$-г илэрхийлнэ.

Та $x - y$-ийн эрэмбийг зүүн хойноос баруун урагш явах, өөрөөр хэлбэл зурсантай перпендикуляр "шүүрдэх шулуун" гэж бодсоноор үүнийг дээрх зургууд дээр төсөөлөхийг оролдож болно.

Энэ нь хэрэв бид идэвхтэй олонлогийг $x$-ээр эрэмбэлж хөтөлбөл нэр дэвшигч $s$-үүд дараалан байрлана гэсэн үг юм. Дараа нь бид хамгийн том $x_s \leq x_p$-г олж, хоёр дахь нөхцөл $x_p - y_p < x_s - y_s$ эвдрэх хүртэл цэгүүдийг $x$-ийн буурах дарааллаар боловсруулж болно (бид үнэндээ $x_p - y_p = x_s - y_s$-г зөвшөөрч болох ба энэ нь тэнцүү координаттай цэгүүдийн тохиолдлыг шийднэ). Бид боловсруулсны дараа шууд олонлогоос хасдаг тул энэ нь $O(n \log(n))$ хорогдуулсан complexity-тэй байхыг анхаарна уу. Одоо бид зүүн хойд чиглэл дэх хамгийн ойрын цэгтэй болсон тул цэгүүдийг эргүүлээд давтана. Ийм байдлаар бид үнэндээ баруун урд чиглэл дэх хамгийн ойрын цэгийг ч олдог болохыг харуулах боломжтой тул бид 8 биш зөвхөн 4 удаа давтаж болно.

Дүгнэвэл бид:

Цэгүүдийг $x + y$-ээр буурахгүй дарааллаар эрэмбэлнэ;
Цэг бүрийн хувьд бид $x \leq x_p$ байх хамгийн том $x$-тэй цэгээс эхлэн идэвхтэй олонлогийг тойрох ба хэрэв $x_p - y_p \geq x_s - y_s$ бол давталтыг тасална. Хүчинтэй $s$ цэг бүрийн хувьд бид жагсаалтдаа $(s,p, d(s,p))$ ирмэгийг нэмнэ;
Бид $p$ цэгийг идэвхтэй олонлогт нэмнэ;
Цэгүүдийг эргүүлээд бүх октантыг тойрох хүртэл давтана.
MST-г авахын тулд ирмэгүүдийн жагсаалтад Крускалын алгоритмыг хэрэглэнэ.

Доор та KACTL-ийнх дээр үндэслэсэн хэрэгжүүлэлтийг олж болно.

struct point {
    long long x, y;
};

// Returns a list of edges in the format (weight, u, v). 
// Passing this list to Kruskal algorithm will give the Manhattan MST.
vector<tuple<long long, int, int>> manhattan_mst_edges(vector<point> ps) {
    vector<int> ids(ps.size());
    iota(ids.begin(), ids.end(), 0);
    vector<tuple<long long, int, int>> edges;
    for (int rot = 0; rot < 4; rot++) { // for every rotation
        sort(ids.begin(), ids.end(), [&](int i, int j){
            return (ps[i].x + ps[i].y) < (ps[j].x + ps[j].y);
        });
        map<int, int, greater<int>> active; // (xs, id)
        for (auto i : ids) {
            for (auto it = active.lower_bound(ps[i].x); it != active.end();
            active.erase(it++)) {
                int j = it->second;
                if (ps[i].x - ps[i].y > ps[j].x - ps[j].y) break;
                assert(ps[i].x >= ps[j].x && ps[i].y >= ps[j].y);
                edges.push_back({(ps[i].x - ps[j].x) + (ps[i].y - ps[j].y), i, j});
            }
            active[ps[i].x] = i;
        }
        for (auto &p : ps) { // rotate
            if (rot & 1) p.x *= -1;
            else swap(p.x, p.y);
        }
    }
    return edges;
}