-
Ladder Decomposition
개요 트리의 Ladder Decomposition은 Heavy-Light Decomposition과 유사하게, 트리를 경로들의 집합으로 분해하는 기법이다. 이번 글에서는 Ladder Decomposition의 정의와 알고리즘, 그리고 이를 응용해서 풀 수 있는 문제에 대해 알아보고자 한다. 정의 Ladder Decomposition를 한 문장으로 줄여 말하면 ‘HLD인데, subtree의 크기가 아니라 높이를 대신 본 것’ 이다. 구체적으로, Ladder Decomposition은 다음과 같은 알고리즘으로 구할 수 있다. 먼저 $h(u)$ 를 정점 $u$를 루트로 하는 서브트리의 높이라 정의하자. 루트부터 DFS를 실행하면서 정점 $v$에 도달 했을 때, $v$의 자식들이 $c_1$, $c_2$,...
-
Zip Tree
서론 Zip Tree는 Robert Tarjan, Caleb Levy, Stephen Timmel이 제시한 랜덤 기반의 Binary Search Tree의 일종이다. 논문에서는 Rotate연산 대신 Zip과 Unzip연산을 통해 트리의 균형을 맞춘다고 소개되어 있지만, 이는 사실 기존에 Treap 자료구조에 대해 다룬 논문에 기재된 Split과 Join연산의 구현과 구조가 동일하다. 본 글에서는 그럼에도 Zip Tree가 널리 알려진 Treap의 형태와 어떤 차이점이 있는지 소개하고, 얻을 수 있는 기대효과를 분석해 보고자 한다. Skip List vs Zip Tree Zip Tree는 Skip List를 Balanced Binary Search Tree로 변환한...
-
Lawson Algorithm을 통한 Delaunay triangulation 구하기
Lawson Algorithm을 통한 Delaunay triangulation 구하기 본 글은 평면 위 점들의 집합을 가장 안정적이고 균일한 삼각형들로 분할하는 Delaunay Triangulation을 종합적으로 탐구한다. 먼저 보로노이 다이어그램과의 관계 및 ‘빈 외접원 속성’을 통해 들로네 삼각분할의 수학적 정의를 명확히 하고, 이어서 고전적인 구축 방법인 Lawson’s algorithm을 분석한다. 마지막으로 이 알고리즘이 왜 항상 정확한 결과를 보장하는지를 증명하기 위해 2차원에서의 문제를 3차원으로 lifting하는 우아한 기법을 사용한다. 1. Delaunay triangulation의 정의와 최적성 평면에 분포된 유한한 점의 집합을 겹치지 않는 삼각형들로 분할하는 triangulation은...
-
Link Cut Tree Subtree Query
안녕하세요, jthis입니다. 이 글에서는 Link-Cut Tree에서 Subtree Query를 효율적으로 수행하는 방법에 대해 소개하겠습니다. 편의상 코드는 Splay Tree를 기준으로 설명하겠습니다. Link Cut Tree Link-Cut Tree는 간선 추가 삭제와 경로 쿼리(Path Query) 를 지원하는 자료구조입니다. 시간복잡도는 amortized $O(\log N)$이며, amortized를 제거하여 $O(\log N)$으로도 가능합니다. 또한, 이 자료구조는 Subtree 연산도 지원할 수 있습니다. 따라서 Top Tree로 해결할 수 있는 대부분의 쿼리 문제를 거의 모두 Link-Cut Tree로 대체할 수 있습니다. Link-Cut Tree는 Splay Tree로만 구현할 수 있다고 생각할 수도...
-
Moving Least Squares Projection 2 - Optimization
지난 글 Moving-Least-Squares-Projection 기존 MLS Projection의 한계 지난 글의 결론 부분에서 간략하게 짚어보았지만, 전에 설명한 방법은 성능적으로도, 그리고 컴퓨팅적으로도 한계가 명확했습니다. 첫째, 측정하고자 하는 물체의 뾰족한 부분이 제대로 표현되지 않고 뭉툭한 형태로 구해집니다. 이는 근본적으로 기존 MLS Projection은 smoothing 기반 기법이기 때문입니다. 아래 정리해본 기존 MLS Projection의 로직을 생각해보면 당연한 결과입니다. 뾰족한 부분에서는 하나의 뚜렷한 Local Approximating Hyperplane이 존재하지 않고, 여러 개의 근사 평면이 서로 교차하게 됩니다. 따라서 알고리즘이 도출하는 결과는 이들 사이의 ‘평균’ 평면이...