rotating calipers (1) 썸네일형 리스트형 100. Rotating Calipers 볼록 껍질을 이용해서 $2$차원 좌표에서 가장 먼 두 점을 찾는 방법을 알아보자. 점이 $n$개인 경우 $\frac{n(n-1)}{2}$개의 쌍을 전부 다 확인하는 방법이 있지만, 점의 개수가 $10$만 개 정도를 넘어가면 속도가 너무 느리다. 이럴 때 사용할 수 있는 방법으로 회전하는 캘리퍼스(Rotating Calipers)라는 알고리즘이 잘 알려져 있다. 캘리퍼스는 길이를 잴 때 사용하는 컴퍼스와 비슷하게 생긴 도구이고, 회전하는 캘리퍼스라고 하면 이런 도구를 회전시키면서 길이를 잰다는 의미로 해석할 수 있다. 실제 알고리즘의 동작 과정도 이와 비슷하며 다음과 같다. 1. 점들의 볼록 껍질을 찾고, 여기에 속하는 점들을 꼭짓점으로 하는 볼록 다각형이 있다고 가정한다. 볼록 껍질에 $k$개의 점이 속.. 이전 1 다음
