Smallest Enclosing Circle/Sphere Problem

관련하여 내가 Codeforces에 올린 Blog article

흔히 가장 먼 두 점의 거리를 2로 나누면 답이 되는 원 또는 구의 반지름이 될 거라 생각하지만, 원의 경우에서부터 다음과 같은 반례가 있다.

Codeforces에 올린 글에 링크 걸어놓은 논문에 의하면 gradient descent 방법으로 최적해를 구할 수 있음이 밝혀져 있다.

따라서 전체 점들에 대한 컨벡스 다각형의 내부의 한 점에서 가장 먼 점으로 계속 이동해 나가다보면(한 term에 이동하는 비율은 단조 감소해야함) 반지름이 최소인 구의 좌표를 알 수 있다.

연습문제로는 내가 만든 BOJ 11930번 문제가 있다.