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