최소동봉원
평면 위에 유한개의 점이 있다. 그 모든 점을 둘러싸는 가장 작은 원을 최소동봉원이라 한다.
알고리즘
아래의 과정을 거쳐 모든 점을 둘러싸는 가장 작은 원을 찾는다.
- 주어진 점들 중에서 무작위로 원의 중심을 정하고, 가장 큰 반지름이 될 수 있는 원 위의 다른 한 점을 주어진 점들 중에서 찾는다.
- 앞서 찾은 원 위의 점은 고정하고, 그 원을 벗어나지 않으며, 모든 점을 포함하는 가장 작은 원을 찾는다.
- 앞서 찾은 원 위의 두 점은 고정하고, 그 두 점을 호의 양 끝점으로 하며 주어진 다른 점들을 원주각의 꼭짓점으로 하여 원주각의 크기들을 재어 가장 작은 원주각이 되는 원을 찾는다.
- 이 때, 세 점으로 나눠진 세 개 호의 길이가 모두 반원보다 작으면 이 원이 찾고자 하는 원이다.
- 단, 여기서 원주각의 크기들이 직각보다 클 때에는 고정된 두 점을 지름으로 하는 원이 찾고자 하는 원이다.
- 앞서 찾은 원 위에 세 점이 있는 경우에 세 점으로 나눠진 세 호 중에서 길이가 반원보다 큰 호가 있을 때, 그 호의 양 끝점을 기준으로 다시 3번 과정을 반복한다.