콘텐츠로 이동

맨해튼 거리

정의

평면 위의 점 $p$와 $q$에 대해 두 점 사이의 거리를 $x$ 좌표 차이와 $y$ 좌표 차이의 합으로 정의할 수 있습니다:

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

이렇게 정의한 거리는 이른바 맨해튼(택시) 기하학에 해당합니다. 이 기하학에서는 점을 맨해튼처럼 잘 설계된 도시의 교차로로 간주하며, 아래 그림과 같이 도로를 따라 수평 또는 수직으로만 이동할 수 있습니다:

Manhattan Distance

이 그림은 한 검은 점에서 다른 검은 점까지 가는 최단 경로 몇 가지를 보여 주며, 모두 길이가 $12$입니다.

이 거리로 할 수 있는 흥미로운 기법과 알고리즘이 여럿 있으며, 여기서는 그중 몇 가지를 소개하겠습니다.

맨해튼 거리에서 가장 먼 점 쌍

$n$개의 점 $P$가 주어질 때 서로 가장 멀리 떨어진 점 쌍 $p,q$를 찾으려 합니다. 즉, $|x_p - x_q| + |y_p - y_q|$를 최대화하려 합니다.

먼저 1차원, 즉 $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$에 대해 확대하는 변환)임을 알 수 있습니다.

다음은 이 변환을 시각적으로 이해하는 데 도움이 되는 그림입니다:

Chebyshev transformation

맨해튼 최소 신장 트리

맨해튼 MST 문제는 평면 위에 몇 개의 점이 주어졌을 때, 모든 점을 연결하면서 가중치의 총합이 최소가 되는 간선들을 찾는 문제입니다. 두 점을 연결하는 간선의 가중치는 두 점 사이의 맨해튼 거리입니다. 편의상 모든 점의 위치가 서로 다르다고 가정합니다. 여기서는 아래 그림처럼 각 점마다 각 팔분면에서 가장 가까운 이웃을 찾아 $O(n \log{n})$에 MST를 구하는 방법을 소개합니다. 이렇게 하면 후보 간선이 $O(n)$개 생기며, 아래에서 보이듯이 이 후보 간선들은 반드시 MST를 포함합니다. 마지막 단계에서는 표준적인 MST 알고리즘을 사용하면 되며, 예를 들어 서로소 집합 유니온을 이용한 Kruskal 알고리즘을 사용할 수 있습니다.

8 octants picture *점 S를 기준으로 한 8개의 팔분면*

여기서 소개하는 알고리즘은 H. Zhou, N. Shenoy, and W. Nichollos (2002)의 논문에서 처음 발표되었습니다. 분할 정복 방식을 사용하는 또 다른 알려진 알고리즘으로 J. Stolfi가 제안한 분할 정복 방식의 알고리즘도 알려져 있습니다. 이 알고리즘 역시 매우 흥미로우며, 각 팔분면에서 가장 가까운 이웃을 찾는 방식만 다릅니다. 두 알고리즘의 복잡도는 같지만, 여기서 소개하는 알고리즘이 구현하기 더 쉽고 상수 인자도 더 작습니다.

먼저 각 팔분면에서 가장 가까운 이웃만 고려해도 충분한 이유를 알아봅시다. 핵심은 점 $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$에 있다고 가정한 뒤, 몇 가지 경우로 나누어 확인합니다. 아래 그림을 보면 이것이 왜 성립하는지 직관적으로 이해할 수 있습니다.

unique nearest neighbor *직관적으로, 팔분면의 제약 때문에 $p$와 $q$가 둘 다 서로보다 $s$에 더 가까울 수는 없습니다*

따라서 핵심 문제는 $n$개의 점 각각에 대해 각 팔분면에서 가장 가까운 이웃을 어떻게 찾느냐입니다.

O(n log n)에 각 팔분면에서 가장 가까운 이웃 찾기

편의상 NNE 팔분면(위 그림의 $R_1$)에 집중합니다. 다른 모든 방향은 입력을 회전하여 같은 알고리즘으로 찾을 수 있습니다.

스위프 라인 방식을 사용합니다. 점들을 남서쪽에서 북동쪽 방향으로, 즉 $x + y$가 감소하지 않는 순서로 처리합니다. 또한 아직 가장 가까운 이웃을 찾지 못한 점들의 집합을 유지하며, 이를 "활성 집합"이라고 부릅니다. 알고리즘을 시각적으로 이해하는 데 도움이 되도록 아래 그림들을 첨부합니다.

manhattan-mst-sweep *검은색 화살표는 라인 스위프의 방향을 나타냅니다. 이 선 아래의 모든 점은 활성 집합에 있으며, 선 위의 점들은 아직 처리되지 않았습니다. 초록색은 처리 중인 점의 팔분면에 있는 점들입니다. 빨간색은 탐색하는 팔분면에 있지 않은 점들입니다.*
manhattan-mst-sweep *이 그림은 점 $p$를 처리한 뒤의 활성 집합을 보여 줍니다. 이전 그림의 초록색 점 $2$개는 north-north-east 팔분면에 $p$가 있었으므로 이미 가장 가까운 이웃을 찾았고, 그래서 더 이상 활성 집합에 없다는 점에 유의하십시오.*

새로운 점 $p$를 추가할 때, 자신의 팔분면에 $p$가 있는 모든 점 $s$에 대해 $p$를 가장 가까운 이웃으로 안전하게 지정할 수 있습니다. $p$가 north-north-east 팔분면에 있으므로 두 점 사이의 거리는 $d(p,s) = |x_p - x_s| + |y_p - y_s| = (x_p + y_p) - (x_s + y_s)$이고, 따라서 이는 참입니다. 정렬 단계 덕분에 이후의 모든 점은 이보다 작은 $x + y$ 값을 가지지 않으므로, $p$가 더 작은 거리를 가진다는 것이 보장됩니다. 그런 다음 이러한 점들을 모두 활성 집합에서 제거하고, 마지막으로 $p$를 활성 집합에 추가할 수 있습니다.

다음 질문은 north-north-east 팔분면에 $p$가 있는 점 $s$를 어떻게 효율적으로 찾느냐는 것입니다. 즉, 다음을 만족하는 점 $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))$이 된다는 점에 주목하십시오. 이제 북동 방향으로 가장 가까운 점을 구했으므로, 점들을 회전시키고 이를 반복합니다. 실제로는 이 방법으로 남서 방향의 가장 가까운 점도 함께 찾게 된다는 것을 보일 수 있으므로, 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$를 활성 집합에 추가합니다;
  • 모든 팔분면을 다 순회할 때까지 점들을 회전하며 반복하십시오.
  • 간선 목록에 Kruskal 알고리즘을 적용하여 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;
}

문제