캘리퍼스는 학교에서 '버니어 캘리퍼스'라고 배웠던 그 도구가 맞다. 알고리즘 동작 과정이 다각형에 캘리퍼스를 돌리는것과 비슷하다고 해서 붙은 이름이다.
영국식 스펠링은 callipers 이다.. 여기에서는 그냥 calipers 로 통일하겠다
'회전하는 캘리퍼스' 라고 번역하는 경우도 있는데, 어차피 그렇게 흔한 알고리즘이 아니고 번역이 완전히 굳어지지도 않은것 같아서 그냥 나한테 좀더 자연스러운 '로테이팅 캘리퍼스' 라고 부르겠다
가장 거리가 먼 두 점
로테이팅 캘리퍼스를 활용하는 가장 대표적인 문제이다.
구현
활용
볼록다각형이 아니라 그냥 점들이 주어졌을때, 가장 거리가 먼 두 점을 찾는 것도, 먼저 볼록 껍질 (Convex Hull)을 구하고 볼록 껍질 위의 점들에 대해서 로테이팅 캘리퍼스를 사용해서 가장 거리가 먼 두점을 구하는 것으로 해결할 수 있다.
볼록 껍질 (Convex Hull)의 특성상, 주어진 점들 중에서 가장 거리가 먼 두 점은, 주어진 점들로 구성한 볼록 껍질의 꼭지점에 포함되게 된다.
이 경우에는 볼록 껍질을 찾는데에 O(nlogn), 로테이팅 캘리퍼스에 O(n)이 걸려서 총 O(nlogn)시간이 걸린다.
실수하기 쉬운 아이디어
얼핏 생각하면 한 점을 기준으로 해서 시계방향으로 다른 점들과의 거리를 비교할때, 거리가 점점 멀어지다가 가까워지는 컨벡스 함수 형태로 나타난다고 잘못 생각할수 있다. 그리고 이 관찰을 바탕으로 기준점에서부터 가장 거리가 먼 점을 삼분 탐색을 통해서 O(logn)에 찾고, 최종적으로는 가장 거리가 먼 두 점을 O(nlogn)에 찾으려고 시도할수도 있다.