회전 캘리퍼스 (Rotating Calipers)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 3분 · 927자/단어 #algorithm #geometry #rotating-calipers

정의

회전 캘리퍼스 (Rotating Calipers) 는 볼록 다각형 위에서 서로 마주보는 두 평행선 (겹지름, antipodal pair) 을 회전시키며 다각형의 최장 거리, 최소 폭, 최대 삼각형 면적 등을 O(N) 에 구하는 기법.

미하일 슐로스만 (M. Shamos) 의 박사 논문 (1978) 에서 처음 제안.

문제 상황과 동기

N 개 점 중 가장 먼 두 점 (farthest pair) 을 구한다.

Naive: 모든 쌍 거리 계산 O(N^2). N=10^5 면 10^10, 불가능.
Convex Hull + Rotating Calipers:
1. Convex hull 구축 O(N log N)
2. Hull 위에서 rotating calipers O(N)
3. 총 O(N log N)

핵심 통찰: 가장 먼 두 점은 항상 볼록 껍질 위에 있다. 캘리퍼스를 360도 회전시키면서 antipodal pair 의 거리를 갱신하면 O(N).

시각화

핵심 아이디어

Antipodal pair (겹지름)

볼록 다각형의 두 꼭짓점에 평행한 두 접선 을 그을 수 있을 때, 그 쌍을 antipodal (마주보는) pair 라고 함.

한 360도 회전 동안 antipodal pair 의 개수 = O(N)
각 pair 의 거리 = max distance candidate

캘리퍼스 회전 (Two-pointer)

1. hull 구축 (반시계 방향)
2. hull[0] 에 대해 가장 먼 hull[j] 찾기 (j = 1)
3. for i = 0..N-1:
       while distance(hull[i], hull[j+1]) > distance(hull[i], hull[j]):
           j = (j + 1) % N
       ans = max(ans, dist(hull[i], hull[j]))
   // i 가 한 바퀴 도는 동안 j 도 많아야 2N 번 움직임 -> O(N)

알고리즘

rotating_calipers(hull):
    N = |hull|
    j = 1
    ans = 0
    for i = 0..N-1:
        while True:
            nxt = (j + 1) % N
            if area(hull[i], hull[i+1], hull[nxt]) <= area(hull[i], hull[i+1], hull[j]):
                break
            j = nxt
        ans = max(ans, dist2(hull[i], hull[j]))
    return sqrt(ans)

// area(a, b, c) = |ccw(a, b, c)| (삼각형 넓이 2배)
// hull[i] - hull[i+1] 변에 대해 가장 먼 점 hull[j]

구현

// Rotating Calipers: farthest pair on convex hull
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Point { ll x, y; };
ll ccw(Point a, Point b, Point c) {
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
ll dist2(Point a, Point b) {
  ll dx = a.x - b.x, dy = a.y - b.y;
  return dx*dx + dy*dy;
}
double rotating_calipers(vector<Point>& hull) {
  int n = hull.size();
  if (n == 2) return sqrt(dist2(hull[0], hull[1]));
  int j = 1;
  ll ans2 = 0;
  for (int i = 0; i < n; i++) {
      int ni = (i + 1) % n;
      while (true) {
          int nj = (j + 1) % n;
          if (abs(ccw(hull[i], hull[ni], hull[nj])) <=
              abs(ccw(hull[i], hull[ni], hull[j]))) break;
          j = nj;
      }
      ans2 = max(ans2, dist2(hull[i], hull[j]));
      ans2 = max(ans2, dist2(hull[ni], hull[j]));
  }
  return sqrt(ans2);
}
int main() {
  vector<Point> hull = {{0,0},{2,0},{3,1},{1,3},{-1,2}};
  cout.precision(6);
  cout << fixed << "Max distance: " << rotating_calipers(hull) << "\n";
}

# Rotating Calipers: farthest pair on convex hull
import math
def ccw(ax, ay, bx, by, cx, cy):
  return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)

def dist2(a, b):
  return (a[0]-b[0])**2 + (a[1]-b[1])**2

def rotating_calipers(hull):
  n = len(hull)
  if n == 2: return math.sqrt(dist2(hull[0], hull[1]))
  j = 1
  ans2 = 0
  for i in range(n):
      ni = (i + 1) % n
      while True:
          nj = (j + 1) % n
          if abs(ccw(*hull[i], *hull[ni], *hull[nj])) <=              abs(ccw(*hull[i], *hull[ni], *hull[j])):
              break
          j = nj
      ans2 = max(ans2, dist2(hull[i], hull[j]))
      ans2 = max(ans2, dist2(hull[ni], hull[j]))
  return math.sqrt(ans2)

hull = [(0,0), (2,0), (3,1), (1,3), (-1,2)]
print(f"Max distance: {rotating_calipers(hull):.6f}")

// Rotating Calipers: farthest pair on convex hull
import java.util.*;

public class Main {
  static class Point { long x, y; Point(long x, long y) { this.x = x; this.y = y; } }
  static long ccw(Point a, Point b, Point c) {
      return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  }
  static long dist2(Point a, Point b) {
      long dx = a.x - b.x, dy = a.y - b.y;
      return dx*dx + dy*dy;
  }
  static double rotatingCalipers(List<Point> hull) {
      int n = hull.size();
      if (n == 2) return Math.sqrt(dist2(hull.get(0), hull.get(1)));
      int j = 1;
      long ans2 = 0;
      for (int i = 0; i < n; i++) {
          int ni = (i + 1) % n;
          while (true) {
              int nj = (j + 1) % n;
              if (Math.abs(ccw(hull.get(i), hull.get(ni), hull.get(nj))) <=
                  Math.abs(ccw(hull.get(i), hull.get(ni), hull.get(j)))) break;
              j = nj;
          }
          ans2 = Math.max(ans2, dist2(hull.get(i), hull.get(j)));
          ans2 = Math.max(ans2, dist2(hull.get(ni), hull.get(j)));
      }
      return Math.sqrt(ans2);
  }
  public static void main(String[] args) {
      List<Point> hull = Arrays.asList(
          new Point(0,0), new Point(2,0), new Point(3,1),
          new Point(1,3), new Point(-1,2));
      System.out.printf("Max distance: %.6f%n", rotatingCalipers(hull));
  }
}

결과

Max distance: 4.472136

복잡도

항목	값
시간 (Convex Hull 포함)	O(N log N) (정렬)
시간 (Hull 위 calipers)	O(N) (two-pointer)
공간	O(N)

j 포인터는 전체 루프에서 최대 2N 번만 전진 -> amortized O(N).

변형 / 활용

1. 최장 거리 (Farthest pair)

가장 먼 두 점. hull + rotating calipers.

2. 최소 폭 (Minimum width)

평행한 두 직선 사이에 hull 을 끼울 때 최소 거리.

3. 최대 면적 삼각형 (Largest triangle in convex polygon)

Antipodal pair 개념 확장: hull[i], hull[j], hull[k] 세 점. O(N^2) (또는 O(N) with rotating calipers 3 개).

4. 최대 내접 사각형

회전 캘리퍼스로 hull 에 내접하는 최대 면적 사각형.

5. Minimum bounding box (최소 면적 외접 직사각형)

hull 의 각 변을 기준으로 캘리퍼스로 나머지 세 변의 위치 O(N) 결정.

함정

1. 정수 vs 실수

거리 제곱을 정수로 유지하다가 최종 sqrt 만 실수. 부동소수점 오차 최소화.

2. Hull 이 점 2개

N=2 면 거리만 출력. calipers 불필요.

3. j 가 i 를 추월

i 와 j 가 동기화되지 않게 주의. while 조건으로 j 가 i 를 넘어가는 것 방지.

4. CCW 부호 일관성

hull 이 반시계(ccw)로 주어져야 area 부호가 일정. Building hull 시 ccw convention 통일.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 9240	로버트 후드	37.2%	kokoa-lab
BOJ 10254	고속도로	23.2%	kokoa-lab
BOJ 1310	달리기 코스	54.1%	kokoa-lab
BOJ 2626	헬기착륙장	23.9%	kokoa-lab
BOJ 10903	Wall construction	61.4%	kokoa-lab

참고

이 글의 용어 (3개)

기하 (Geometry) 기본algorithm: 정의 Computational Geometry 는 점, 선, 다각형 등 기하 객체를 컴퓨터로 처리하는 알고리즘 분야. PS 에서는 2D 평면 위의 정수 좌표 가 주로 다루어지며,…
볼록 껍질 (Convex Hull)algorithm: 정의 볼록 껍질 (Convex Hull) 은 주어진 점 집합 P 를 모두 포함하는 최소 크기의 볼록 다각형. 즉 P 의 어떤 점도 다각형 외부에 있지 않고, 다각형의 꼭짓점은 P…
Geometry Basic: 벡터, CCW, 외적, 내적algorithm: 정의 기하 알고리즘의 밑바탕. 대부분의 2D/3D 기하 문제는 벡터 연산, 내적/외적, CCW 판정 세 가지의 조합으로 풀립니다. 벡터 2D 벡터: 두 점 $A = (ax, ay…