-
Geometric spanning tree
Geometric Spanning Tree $d$ 차원 좌표공간 상에 크기 $N$ 의 점 집합 $S$ 가 주어졌을 때, 집합 $S$ 를 정점 집합으로 하며 각 정점 쌍마다 두 점의 거리를 가중치로 한 그래프를 생각할 수 있다. 이러한 그래프에서 최소 스패닝 트리를 찾는 문제를 Minimum Geometric Spanning Tree 라고 한다 (Encyclopedia of Algorithms 533p). 두 정점의 “거리” 를 지정하는 방법은 여러 가지가 존재하고, 이 거리계를 어떻게 지정하느냐에 따라서 문제를 해결하는 양상이 많이 달라진다. 일반적으로 사용하는 거리계는 $L_1$ metric...
-
장애물을 포함하지 않는 가장 큰 직사각형 찾기
장애물을 포함하지 않는 가장 큰 직사각형 찾기 Motivation 계산기하에서 장애물을 포함하지 않는 가장 큰 도형을 찾는 것은 핵심적인 문제 중 하나이다. 다양한 거리계, 그리고 도형의 모양에 따라서 서로 다른 알고리즘들이 존재한다. 예를 들어서, 다음과 같은 문제들을 생각할 수 있다. A) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 원은 무엇인가? B) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 직사각형은 무엇인가? C) $n$ 개의 점들이 있을 때,...