Intro
Minimum Spanning Tree, 우리말로는 최소 신장 트리는 잊을 만 하면 등장하는 주제 중 하나입니다. 최소 신장 트리를 구하기 위해서는 보통 두 가지 알고리즘이 사용됩니다. 하나는 크루스칼 알고리즘으로 $O(E \log E)$의 복잡도를 가지고, 나머지 하나는 프림 알고리즘으로 $O(E \log V)$의 시간복잡도를 가집니다. 하지만 이 두 알고리즘 모두 한 가지 단점을 가지고 있는데, 일단 알고리즘을 수행하려면 모든 간선을 읽어야 한다는 것입니다. 이게 왜 문제인지 의아해 하실 수도 있지만, 그래프가 완전 그래프에 가깝고, 가중치를 매기는 방식이 별도로 존재하는 것과 같이 특수한 상황에서는 모든 간선을 다 보는 것만으로도 시간 초과가 나서 일부 간선만을 보아야만 문제를 해결할 수 있는 경우가 있습니다. 예를 들어서 간선이 정점에 부여된 가중치의 XOR 값 만큼의 비용을 가지는 경우를 들 수 있겠습니다. 하지만 오늘 다룰 케이스는 그 중에서 간선의 가중치가 정점 사이의 유클리디안 거리인 케이스인 Eucliden MST, 줄여서 EMST입니다. 이 글에서는 정점이 $n$개 있는 2차원 EMST 문제를 Naive한 시간복잡도인 $O(n^2 \log n)$보다 빠르게 해결하는 법에 대해 서술합니다.
EMST를 해결하기 위해서
EMST를 해결하기 위해서 우리는 다음과 같은 내용들을 공부해야 합니다. 아니, 사실 단 하나만 공부하면 됩니다. 바로 델루네 삼각분할입니다. 델루네 삼각분할을 간단하게 요약하면 2차원 평면에 분포하는 점들을 선분으로 적절하게 이어 삼각형으로 쪼개는데, 각 삼각형들이 꼭짓점을 제외한 다른 점을 포함하지 않는 분할입니다. 왜 이 델루네 삼각분할이 EMST에 큰 영향을 끼치느냐 하면, EMST에 포함되는 간선들의 집합은 반드시 델루네 삼각분할을 통해 찾을 수 있는 간선 집합의 부분집합이기 때문입니다. 델루네 삼각분할을 통해 찾아지는 간선 집합의 크기가 충분히 작다면, 이를 이용해서 전체 시간복잡도 또한 작게 bound시킬 수 있을 것입니다. 그러면 이 사실을 증명하기 위해서, 델루네 삼각분할에 대해서 간단하게 먼저 공부해봅시다.
델루네 삼각분할
델루네 삼각분할(Delaunay Triangulation)은 보로노이 다이어그램과 듀얼 그래프 관계입니다. 델루네 삼각분할의 각 삼각형의 외심은 각각 보로노이 다이어그램의 꼭짓점이 됩니다. 또 두 삼각형이 델루네 삼각형에서 변을 공유한다면, 그 두 외심은 보로노이 다이어그램에서 간선으로 이어져 있습니다.
델루네 삼각분할을 수행하면, 다음과 같은 성질들을 찾을 수 있게 됩니다. 재미를 위해서 델루네 삼각분할의 많은 성질들을 적어 놓았습니다. 그런 고로 이 성질 중 EMST를 해결할 때 사용하는 성질은 극히 일부라는 점에 유의하세요.
- 당연하겠지만, 삼각분할 후 만들어지는 모든 조각을 모으면 이는 정점들의 볼록 껍질이 됩니다.
- 델루네 삼각분할은 정점들을 $d$차원 공간에서 $O(n^ {\lceil d/2 \rceil)})$개의 조각으로 쪼갭니다. 이는 매우 중요한 성질로, 우리는 2차원 공간을 다루기 때문에 정점들은 최대 $O(n)$개의 조각으로 쪼개집니다.
- 특히 2차원 공간에서, convex hull이 $b$개의 선분으로 이루어져 있다면 정점들의 삼각분할은 최대 $2n-2-b$개의 삼각형을 가집니다. 이는 Euler characteristic으로 증명할 수 있습니다.
- 평면에서 델루네 삼각분할은 최소 각도를 최대화합니다. 다른 방법으로 어떻게 삼각분할을 하더라도, 그 삼각분할의 최소 각도는 델루네 삼각분할의 최소 각도보다 클 수 없습니다. (최대 각도를 최소화 하지는 않습니다.)
- 어떠한 델루네 삼각분할로 만들어진 삼각형도 그 외접원이 다른 정점을 내부에 포함하지 않습니다.
- 비슷하게, 만약 어떤 원이 두 정점을 지나면서 내부에 아무 정점을 포함하지 않는다면, 그 두 정점을 잇는 간선은 델루네 삼각분할을 구성하는 선분 중 하나입니다. 이는 EMST 증명에 있어서 핵심적인 성질입니다.
- Nearest Neighbor Graph는 델루네 삼각분할의 부분그래프입니다. 이 성질을 이용해서 K-d Tree가 하는 일을 일부 대체할 수 있습니다.
델루네 삼각분할을 실제로 Problem Solving에서 구현해야 한다면, 다음과 같은 알고리즘을 사용할 수 있습니다. 구현이 쉽지 않고 선형대수와 계산 기하에 관한 지식도 요구하지만, 원리 자체는 이해하기 힘든 수준이 아니므로 한번쯤 읽어보셔도 좋을 것 같습니다.
EMST와 델루네 삼각분할의 접합
앞에서 EMST에 포함되는 간선들의 집합은 반드시 델루네 삼각분할을 통해 찾을 수 있는 간선 집합의 부분집합이라고 언급한 바가 있습니다. 고로 EMST는 델루네 삼각분할의 부분그래프라는 말인데, 언뜻 보기에는 자명하지 않아 보입니다. 하지만 다음과 같은 과정을 통해 생각보다 간단하게 증명할 수 있습니다.
Claim: 점 집합 $P$의 Euclidean MST $E$는 $P$의 델루네 삼각분할 $D(P)$의 부분그래프이다.
Proof:
귀류법을 사용합니다. $p_i, p_j \in P$에 대해서 $\overline{p_i p_j} \in E$이고 $\overline{p_i p_j} \notin D(P)$라고 합시다. 위에서 언급한 델루네 삼각분할의 성질 중 만약 어떤 원이 두 정점을 지나면서 내부에 아무 정점을 포함하지 않는다면, 그 두 정점을 잇는 간선은 델루네 삼각분할을 구성하는 선분 중 하나라는 성질을 사용합시다. 그러면 $\overline{p_i p_j }$을 지름으로 하는 원 안에는 반드시 하나 이상의 점이 있음을 알 수 있습니다. 그 중 하나를 임의로 골라 $p_k$라고 합시다.
$\overline{p_i p_j}$를 $E$에서 제거하면, $E$는 트리이므로 2개의 컴포넌트로 쪼개지게 됩니다. 그 중 하나는 $p_i$를 포함하고 나머지 하나는 $p_j$를 포함합니다. 일반성을 잃지 않고 $p_k$가 두 컴포넌트 중 하나인 $p_i$가 존재하는 컴포넌트에 속한다고 합시다. 이 때 $\overline{p_j p_k}$를 $E$에 추가한다면 어떻게 될까요? $p_i$와 $p_k$는 같은 컴포넌트에 속해 있으니 이 간선을 추가하면 두 컴포넌트는 다시 합쳐지게 됩니다. 그런데 $p_k$는 $\overline{p_i p_j }$을 지름으로 하는 원 안에 있으므로, 자명히 $\vert \overline{p_i p_j} \vert > \vert \overline{p_j p_k}\vert $입니다. 결국 원래 트리는 MST가 아니었으니 가정에 모순이고, Claim이 성립합니다.
이제 EMST가 델루네 삼각분할의 부분그래프라는 것을 알았으니, 델루네 삼각분할을 진행한 후 삼각분할에 속하는 간선들에 한해서만 크루스칼과 같은 통상적인 MST 알고리즘을 수행해도 전체 간선에 대해서 수행한 것과 동일한 결과를 얻을 수 있다는 것 또한 알 수 있습니다. 델루네 삼각분할은 최적화된 알고리즘을 통해 $O(n \log n)$ 시간에 찾아줄 수 있고, 랜덤 알고리즘을 얹으면 평균적으로 $O(n \log \log n)$시간에도 찾을 수 있습니다. 그렇다면 이 삼각분할을 수행한 간선들에 대해서 크루스칼 알고리즘을 수행하는 데는 얼마의 시간이 걸릴까요? 델루네 삼각분할은 2차원 평면에서 최대 $O(n)$개의 삼각형을 만들고 각 삼각형은 최대 3개의 변을 가지기 때문에 간선의 개수도 $O(n)$개가 됩니다. 따라서 크루스칼 알고리즘을 수행하는 데도 $O(n \log n)$ 시간이 걸립니다.
결과적으로 위에서 서술한 모든 과정을 $O(n \log n)$ 시간 안에 빠르게 수행할 수 있습니다.
더 나아가기
델루네 삼각분할 외에도 다음과 같은 방법들을 사용할 수 있습니다.
- Well-seperated pair decomposition을 사용하여 찾아 줄 수 있습니다. 기본적인 접근은 쿼드 트리를 이용해 클러스터를 분리한 뒤, 분할 정복처럼 각각의 클러스터를 이어 MST로 만들어 주는 방식입니다.
- 2차원 뿐만이 아닌 더 고차원인 Euclidean MST 문제에서, 보르부카 알고리즘을 조금 더 효율적으로 활용하여 문제를 해결할 수 있습니다. 보르부카 알고리즘은 잘 알려지지 않았지만 특수한 경우의 MST 문제를 효율적으로 해결할 수 있는 방법 중 하나입니다. 다음 논문에서 Dual-Tree 보르부카 알고리즘을 활용하여 EMST 문제를 해결하는 과정을 볼 수 있습니다. 매우 복잡하고 난해하기 때문에, Problem Solving으로의 적용 가능성은 없을 것 같습니다.