위키득계정 ↗
기술

최소 포함 원

최소 포함 원기술
영어
Minimum enclosing circle
포함 조건
모든 점이 내부 또는 경계에 위치
최소화 대상
반지름
대표 계산법
무작위 순서를 이용한 웰즐 알고리즘
최소 포함 원은 평면의 주어진 점을 모두 내부 또는 경계에 포함하는 원 가운데 반지름이 가장 작은 원이다. 유한한 비어 있지 않은 점 집합에 대해 하나로 결정되며, 모든 입력 점이 원주 위에 있어야 하는 것은 아니다.

외접원과의 차이

삼각형의 외접원은 세 꼭짓점을 모두 원주 위에 놓는다. 최소 포함 원에서는 일부 점이 내부에 있어도 된다. 예를 들어 (−2,0), (2,0), (0,1)을 포함하는 최소 원은 중심이 원점이고 반지름이 2다. 세 번째 점은 원주가 아니라 내부에 놓인다.

반지름의 하한

어떤 두 점을 모두 포함하는 원의 지름은 두 점 사이의 거리보다 작을 수 없다. 앞의 예에서는 양 끝점의 거리가 4이므로 반지름이 적어도 2여야 한다. 반지름 2인 원이 나머지 점까지 포함하므로 이 하한을 실제로 달성하며 최소임을 알 수 있다.

경계점과 계산

최소 원은 경계에 있는 소수의 점으로 결정할 수 있다. 점이 하나뿐이면 반지름은 0이고, 두 점이 결정하는 경우에는 그 선분이 지름이 된다. 세 점이 필요한 경우에는 세 점의 외접원을 사용한다. 공선인 세 점에는 보통의 외접원이 존재하지 않으므로 별도로 처리한다.

무작위 알고리즘

웰즐 알고리즘은 점의 순서를 무작위로 정하고, 현재 원 밖에 나타나는 점을 경계 조건에 반영하며 원을 갱신한다. 기대 시간 복잡도는 O(n)이지만 모든 입력 순서에서 선형 시간이 보장된다는 뜻은 아니다. 부동소수점 계산에서는 원 안의 점과 경계점의 판정을 일관되게 처리해야 한다.

관련 문서

외접원 / 원 / 지름 / 유클리드 거리 / 시간 복잡도 / 볼록 껍질