계산기하학

수치해석 컴퓨터 그래픽스 마지막 수정: 2026-08-18 04:12:07

1. 개요[편집]

계산기하학 Computational Geometry
대상	점 · 선분 · 다각형 · 다면체 · 초평면 배열
세 패러다임	평면 스윕 · 분할정복 · 무작위 증분
표준 하한	Ω(n log n) (대수적 결정트리 모형)
진짜 난제	퇴화(degeneracy) · 수치 강건성
대표 라이브러리	CGAL · LEDA · GEOS · Clipper
주 응용	메시 생성 · 충돌 감지 · GIS · 로봇 경로계획

계산기하학(computational geometry)은 점·선분·다각형·다면체 같은 기하학적 대상을 다루는 알고리즘의 설계와 복잡도 해석을 연구하는 전산학의 한 분야다. “두 점 중 가까운 쪽”이 아니라 ” $n$ 개 점 중 가장 가까운 쌍을 $O(n\log n)$ 에”, “선분 $n$ 개의 교점 $k$ 개를 $O((n+k)\log n)$ 에” 같은 문장을 생산하는 것이 이 분야의 일이다. 1970년대 중후반 샤모스(M. Shamos)의 학위논문이 이름과 뼈대를 함께 세웠고, 프레파라타-샤모스(1985)와 더 베르흐 등의 교과서를 거치며 지금의 커리큘럼이 굳었다.

이 분야가 다른 알고리즘 분야와 결정적으로 다른 지점은 하나의 문제 안에 조합적 층과 수치적 층이 동시에 존재한다는 것이다. 답의 본체는 “어느 삼각형이 어느 삼각형과 이웃인가”, “이 점이 이 다각형 안인가” 같은 위상·조합 정보인데, 그 정보를 뽑는 유일한 통로는 좌표에 대한 부동소수점 산술이다. 그래서 오차가 아무리 작아도 판정의 부호가 한 번 뒤집히면 답이 조금 틀리는 게 아니라 자료구조 자체가 모순에 빠진다. 이 문제는 정확 술어 문서에서 따로 다룬다.

2. 세 가지 패러다임[편집]

기하 알고리즘의 설계 기법은 놀랍도록 적다. 교과서 한 권이 사실상 아래 셋의 변주다.

2.1. 평면 스윕[편집]

수직선 하나를 왼쪽에서 오른쪽으로 쓸고 지나가며, 스윕선이 지금 만나고 있는 것들만 정렬된 상태로 유지하는 기법. 2차원 문제를 “1차원 문제 + 시간”으로 낮추는 환산이다. 구성 요소는 둘뿐이다.

이벤트 큐 — 스윕선의 상태가 바뀌는 $x$ 좌표들. 우선순위 큐로 관리하며, 알고리즘 도중에 새 이벤트가 추가될 수 있다.
상태 구조 — 스윕선과 현재 교차 중인 대상들의 순서. 보통 균형 이진 탐색 트리.

대표 사례가 벤틀리-오트만 선분 교차(1979)다. 두 선분이 교차하려면 교차 직전에 스윕선 위에서 반드시 이웃이 된다는 관찰이 전부다. 그래서 삽입·삭제·교차 이벤트마다 새로 이웃이 된 쌍만 검사하면 되고, 교점이 $k$ 개일 때 $O((n+k)\log n)$ 시간· $O(n)$ 공간에 전부 찾는다.¹ 전수 비교 $O(n^2)$ 와의 차이는 실측에서도 그대로 나온다. 같은 틀로 보로노이 다이어그램을 $O(n\log n)$ 에 만드는 것이 포춘의 스윕(1987)이고, 이때 스윕선 대신 포물선들의 해안선(beach line)을 굴린다.

2.2. 분할정복[편집]

점 집합을 좌표 중앙값으로 반으로 갈라 각각 풀고, 경계 근처의 상호작용만 병합에서 처리한다. 병합이 선형이면 $O(n\log n)$ 이 나온다.

교과서의 첫 예제인 최근접 쌍 문제가 정확히 이 모양이다. 왼쪽 해 $\delta_L$ , 오른쪽 해 $\delta_R$ 를 구한 뒤 $\delta=\min(\delta_L,\delta_R)$ 로 두면, 분할선 양쪽으로 폭 $\delta$ 인 띠 안의 점들만 남는다. 이 띠의 점들을 $y$ 로 정렬해 훑으면 각 점은 뒤따르는 상수 개(고전적으로 7개) 점하고만 비교하면 충분하다 — $\delta \times 2\delta$ 짜리 직사각형 안에 서로 $\delta$ 이상 떨어진 점이 상수 개밖에 못 들어가기 때문이다. 병합이 $O(n)$ 이므로 전체 $O(n\log n)$ .

같은 골격이 볼록 껍질의 3차원 프레파라타-홍 알고리즘, 다차원 최근접 질의, 그리고 분할 정복 일반론에 그대로 재활용된다.

2.3. 무작위 증분[편집]

대상을 임의 순서로 하나씩 집어넣으며 답을 갱신한다. 최악의 입력 순서가 나쁠 뿐이지 무작위 순서는 거의 항상 좋다는 것이 요점이라, 입력이 아니라 알고리즘이 주사위를 던진다.

분석 도구가 예쁘다. 후방 분석(backward analysis)은 ” $i$ 번째 삽입의 비용”을 직접 세는 대신 ” $i$ 개가 이미 들어간 상태에서 마지막에 들어온 것이 하필 방금 그것일 확률”을 센다. 예를 들어 들로네 삼각분할의 무작위 증분에서, 점 하나를 지우면 사라지는 삼각형 수의 기댓값은 $i$ 개 점의 삼각형 총수 $O(i)$ 를 $i$ 로 나눈 $O(1)$ 이다. 따라서 구조 변경의 총량이 $O(n)$ 이고, 점 위치 결정 비용까지 합쳐 기댓값 $O(n\log n)$ . 클락슨-쇼어(1989)의 무작위 표본추출 이론이 이 계열 전체의 일반 틀을 제공한다.

무작위 증분이 실무에서 사랑받는 이유는 복잡도보다 코드가 짧아서다. 스윕은 이벤트 큐와 상태 구조의 동기화가 지저분하고 분할정복은 병합 단계가 까다로운데, 증분법은 “삽입 + 국소 수선”이라 자료구조 하나면 끝난다. CGAL의 들로네·사다리꼴 분할 구현이 전부 이 계열이다.

3. 대표 문제군[편집]

문제	최적 복잡도	주 기법
볼록 껍질 (2D)	O(n log h) 출력 민감	정렬 + 스택, 하이브리드
선분 교차 보고	O(n log n + k)	평면 스윕
최근접 쌍	O(n log n)	분할정복
들로네 삼각분할 · 보로노이 다이어그램	O(n log n)	스윕 / 무작위 증분 / 리프팅
단순다각형 삼각분할	O(n)	사다리꼴 분해(샤젤 1991)
점 위치 결정	전처리 O(n), 질의 O(log n)	사다리꼴 지도 · 지속 자료구조
직선 $n$ 개의 배열 구성	Θ(n²)	증분 + 존 정리
다각형 가시성	O(n)	스택 기반 스윕

점 위치 결정(point location)은 “이 좌표가 평면 분할의 어느 면에 속하는가”를 묻는 질의다. GIS의 “이 주소는 어느 행정동인가”가 그대로 이 문제이며, 커크패트릭(1983)의 계층 구조나 무작위 증분 사다리꼴 지도로 $O(n)$ 공간· $O(\log n)$ 질의가 나온다. 사르낙-타잔(1986)의 지속(persistent) 탐색트리를 쓰면 스윕의 각 시점 상태를 통째로 보관해 같은 성능이 나오는데, “시간축을 자료구조에 접어 넣는다”는 발상이 그 자체로 유명하다.

단순다각형 삼각분할은 이 분야의 상징 같은 문제다. $O(n\log n)$ 은 1978년에 나왔고, 1991년 샤젤이 선형 시간 알고리즘으로 문제를 닫았다. 다만 그 알고리즘은 구현한 사람이 거의 없을 만큼 복잡해서, 실무는 자이델(1991)의 기대 $O(n\log^* n)$ 무작위 알고리즘이나 아예 $O(n^2)$ 짜리 귀 자르기(ear clipping)를 쓴다. 이론적 최적성과 실용성이 정면으로 갈라지는 이 분야의 대표적 사례다.²

4. 출력 민감 복잡도[편집]

기하 문제는 입력 크기 $n$ 만으로 비용이 정해지지 않는 경우가 흔하다. 선분 $n$ 개의 교점 수 $k$ 는 0부터 $\binom{n}{2}$ 까지, 볼록 껍질의 꼭짓점 수 $h$ 는 3부터 $n$ 까지 아무 값이나 된다. 그래서 복잡도를 $n$ 과 출력 크기의 함수로 쓰는 출력 민감(output-sensitive) 분석이 표준이 됐다.

볼록 껍질: $O(n\log h)$ — 챈(1996), 커크패트릭-자이델(1986). $h$ 가 작으면 거의 선형이다.
선분 교차: $O(n\log n + k)$ — 샤젤-에델스브루너(1992)가 벤틀리-오트만의 $\log$ 를 걷어냈다.
다면체 볼록 껍질: 차원 $d$ 에서 면 수가 $\Theta(n^{\lfloor d/2\rfloor})$ 까지 커질 수 있으므로(맥멀런의 상계 정리), 고차원에서는 “빠른 알고리즘”이라는 말 자체가 무의미해진다.

하한 쪽도 정리되어 있다. 대수적 결정트리 모형에서 원소 유일성 판정이 $\Omega(n\log n)$ 이고, 최근접 쌍·볼록 껍질·들로네 삼각분할이 전부 여기로 환산되므로 $\Omega(n\log n)$ 이 걸린다. 한편 “세 점이 한 직선 위에 있는가”, “최소 넓이 삼각형” 같은 문제군은 3SUM 난해로 분류되어 사실상 $n^{2-o(1)}$ 하한을 조건부로 물려받는다.³

5. 퇴화와 강건성 — 이 분야의 진짜 난제[편집]

논문은 대개 일반 위치(general position)를 가정한다. 어떤 세 점도 공선이 아니고, 어떤 네 점도 한 원 위에 있지 않으며, 같은 좌표를 가진 점이 없고, 어떤 두 점도 $x$ 좌표가 같지 않다는 가정이다. 이 가정 아래 알고리즘은 5쪽이면 기술된다.

현실의 입력은 정확히 그 반대다. CAD 모델은 축에 정렬되어 있고, GIS 데이터는 같은 경계선을 두 폴리곤이 공유하며, 게임 레벨은 좌표가 격자에 스냅되어 있다. 퇴화는 예외가 아니라 기본값이다. 그래서 실제 코드에서는 다음 두 가지가 분량의 절반 이상을 먹는다.

퇴화 처리. 공선·공면·중복 좌표를 각각 분기해서 다루거나, 무한소 섭동(Simulation of Simplicity)으로 입력을 상징적으로 흔들어 퇴화를 없앤다. 후자는 코드가 깔끔해지는 대신, “경계 위의 점”이 일관되게 안쪽 또는 바깥쪽으로 밀려나므로 사용자가 기대한 답과 다를 수 있다.
부호의 정확성. 방향 판정 $\mathrm{orient2d}$ 와 내접원 판정 $\mathrm{incircle}$ 의 부호가 틀리면 위상이 깨진다. “볼록 껍질이 오목해진다”, “삼각분할에 구멍이 뚫린다”, “플립 루프가 영원히 안 끝난다”가 전부 이 한 줄에서 나온다.

\mathrm{orient2d}(a,b,c) = \operatorname{sign} \begin{vmatrix} b_x - a_x & b_y - a_y \\ c_x - a_x & c_y - a_y \end{vmatrix}

여기서 흔한 오해가 ” $|\det| < \varepsilon$ 이면 0으로 본다”는 톨러런스 방식인데, 이러면 판정이 추이적이지 않게 되어 상황이 오히려 나빠진다. $a\approx b$ , $b\approx c$ 인데 $a\not\approx c$ 인 배치가 곧바로 자료구조를 모순에 빠뜨리기 때문이다. 올바른 처방은 오차를 작게 만드는 것이 아니라 부호를 정확히 맞히는 것이며, 이것이 정확 술어와 정확 기하 계산(EGC) 패러다임의 출발점이다. 부동소수점 연산의 조건수 감각으로는 이 문제를 이해할 수 없다는 점이 중요하다 — 여기서 요구되는 것은 상대오차가 아니라 이산적 판정의 무결성이다.

6. 자료구조[편집]

기하 알고리즘은 답을 “삼각형 목록” 같은 평평한 배열이 아니라 이웃 관계를 담은 그래프로 들고 다닌다.

DCEL(doubly connected edge list) — 평면 분할을 반쪽 모서리(half-edge)들로 표현한다. 각 반모서리가 쌍(twin)·다음·이전·시작정점·왼쪽면을 들고 있어 “이 면의 경계를 한 바퀴 돌기”, “이 정점 주위 모서리를 순회하기”가 $O(1)$ 상수로 이어진다. 메시 처리·불리언 연산·메시 생성의 공통 뼈대이며, 3차원 확장이 반모서리 메시다.
배열(arrangement) — 직선·곡선들이 평면을 쪼갠 전체 세분. 직선 $n$ 개면 면 $\Theta(n^2)$ 개이고, 존 정리(직선 하나가 지나는 면들의 총 복잡도가 $O(n)$ )를 써서 증분 구성이 $O(n^2)$ 에 끝난다. 쌍대 변환으로 점-직선을 맞바꾸면 “가장 많은 점을 지나는 직선”류 문제가 배열 문제로 번역된다.
공간 분할 트리 — kd-트리·BSP·경계 볼륨 계층은 최악 복잡도 보장보다 실측 성능을 노린 실무 계열이다. 자세한 것은 공간 분할 자료구조 참고.

7. 응용[편집]

메시 생성. 들로네 삼각분할의 최소각 최대화 성질이 유한요소 격자 품질과 직결되므로, 들로네 정련(Delaunay refinement)이 유한요소법·유한체적법 전처리의 표준이 됐다. 여기서 “각도 하한을 보장한다”는 정리를 코드가 실제로 지키려면 인서클 술어가 정확해야 한다 — 이론과 강건성이 만나는 지점이다.
충돌 감지. 브로드 페이즈는 스윕-앤-프룬(1차원 스윕의 재활용)과 경계 볼륨 계층, 내로 페이즈는 GJK 알고리즘과 민코프스키 합이다. 오목 메시를 물리 엔진에 넣기 전에 볼록 분해로 쪼개는 것도 계산기하 작업.
GIS. 지도 중첩(map overlay)은 두 평면 분할의 배열을 구성해 면을 재조합하는 문제이고, 폴리곤 불리언 연산·버퍼(민코프스키 합)·최근접 시설 질의(보로노이 다이어그램)가 전부 여기 속한다. 좌표가 도(degree) 단위 실수인 데다 데이터 제공자가 서로 다른 반올림을 쓰기 때문에, GIS는 퇴화와 강건성 문제가 가장 잔인하게 드러나는 현장이기도 하다.
로보틱스와 경로 계획. 로봇 모양을 장애물에 민코프스키 합으로 흡수해 점으로 만드는 구성공간 환산, 가시성 그래프, 내비게이션 메시 생성이 계산기하의 응용이다.
그래픽스. BSP 트리에 의한 가시성 정렬, 클리핑, 레이 트레이싱 가속 구조, 마칭 큐브의 등위면 추출이 전부 기하 알고리즘이다.

라이브러리로는 CGAL이 사실상 표준이다. 정확 술어와 임의 정밀도 커널을 교체 가능한 템플릿 인자로 빼 둔 설계가 특징인데, 그 덕에 “빠르지만 가끔 틀리는 커널”과 “느리지만 항상 맞는 커널”을 컴파일 스위치 하나로 바꿀 수 있다. 2차원 폴리곤 불리언 전용으로는 Clipper, GIS 쪽에서는 GEOS/JTS가 널리 쓰인다.

8. 관련 문서[편집]

벤틀리-오트만은 “출력에 비례하는 시간”을 실현한 초기 사례로 자주 인용되지만, 구현 난이도로도 유명하다. 세 선분이 한 점에서 만나거나, 선분이 겹쳐 놓이거나, 교점의 $x$ 좌표가 다른 이벤트와 정확히 같아지는 순간 상태 구조의 순서가 정의되지 않는다. 논문은 “일반 위치를 가정한다” 한 줄이면 끝나는데, 코드는 그 한 줄이 없어서 두 배로 길어진다. ↩
샤젤의 선형 시간 삼각분할은 “존재는 증명됐으나 아무도 안 쓰는 알고리즘”의 대명사로 통한다. 정작 게임·그래픽스 현장에서 가장 많이 도는 것은 최악 $O(n^2)$ 인 귀 자르기인데, 다각형 정점이 수천 개를 넘는 일이 드물고 코드가 50줄이면 끝나기 때문이다. 복잡도 표와 실제 콜스택은 자주 다른 세상에 산다. ↩
3SUM 난해는 “3SUM 이 $\Theta(n^2)$ 이다”라는 가정 위에 서 있었는데, 2014년 그뢴룬-페티가 살짝 준이차 시간 알고리즘을 내면서 가정이 약해졌다. 그래도 $n^{2-o(1)}$ 수준의 조건부 하한으로서의 실용적 의미는 그대로다 — “이 문제로 이차 시간을 크게 깨려는 시도는 3SUM 부터 깨고 오라”는 뜻이니까. ↩