📂위상데이터분석

벨츨 알고리즘: 최소내포디스크 문제의 해법

문제

최소 내포 디스크

$n > d$ 라고 하자. $d$차원 유클리드 공간에서 주어진 유한 집합 $P = \left\{ p_{k} \right\}_{k=1}^{n} \subset \mathbb{R}^{d}$ 에 대해 다음과 같은 최적화 문제를 최소 내포 디스크 문제^{smallest Enclosing Disk Problem}라 한다. $$ \begin{matrix} \text{Minimize} & r \ge 0 \\ \text{subject to} & \left\| c - p_{k} \right\|_{2} \le r \end{matrix} \\ c \in \mathbb{R}^{d} , k = 1, \cdots , n $$

팁

다음은 정확히 정리라고 할만큼 거창한 건 아니지만 이 문제를 다룰 때 알아두면 좋은 팩트들이다.

• $P$ 가 아핀독립이라면, 디스크의 바운더리^boundary에는 $P$ 의 점이 최소 $2$ 에서 최대 $d+1$ 개만큼 존재한다. 쉽게 말해 점들이 겹쳐져 있거나 어떤 일직선 상에 세 개 이상 놓이거나 하지 않는 이상 정확히 $2 \le m \le d+1$ 개의 점으로 최소내포디스크가 유일하게 존재하게끔 결정된다.
  • 예를 들어서 $d = 2$차원 평면에서 원은 정확히 세 개의 점으로 유일하게 결정된다.
• 일반적으로 $n > d+1$ 개의 점이 주어져 있을 때, 알고리즘^algorithm이 아닌 명시적인 공식^{explicit formula}를 찾아내는 것은 불가능한 것으로 사료된다. 위에서 언급한, 바운더리에서 최소내포디스크를 유일하게 존재하게끔 결정하는 점들을 서포트^support라 부르는데, 그냥 점들만 가지고는 누가 서포트인지 알 방도가 없기 때문이다.
  • 이렇게 테두리에 있는 점을 서포트라고 부르는 점은 기하 문제에서 흔하다. 서포트 벡터 머신에서 서포트가 바로 테두리에 있는 점을 의미한다.
• 따라서 이 문제를 푸는 알고리즘을 개발한다는 것은 곧 바운더리에 있는 서포트를 찾는 것을 보장하거나, 그것을 빠르게 찾는 방법에 대한 연구라고 해도 과언이 아니다. 다만 현재 쓰이는 알고리즘에서 그 근본적인 아이디어는 거의 벨츨의 것을 기반으로 하고 있어 그 개선이나 변종을 묶어 그냥 벨츨 알고리즘^{welzl Algorithm}이라 하며¹, 적어도 이 포스트에서 소개되는 후속 연구들은 모두 그 계보를 따르고 있다.

해법

벨츨 알고리즘 ²

벨츨 알고리즘^{welzl Algorithm}은 최소내포디스크 문제를 푸는 재귀적인^recursive 해법이다. 기본적으로 점을 하나씩 넣었다가 뺐다가 하면서 서포트를 찾고, 그렇게 얻어지는 디스크가 주어진 모든 점을 내포하는지 확인하는 것을 반복한다.

점이 $n \le d+1$ 개만큼 주어져 있을 때 정확히 이들을 내포하는 디스크를 찾는 것은 상대적으로 간단하므로 이러한 함수는 존재한다고 가정한다. 실제 구현에서는 이것이 생각만큼 만만하지만은 않으나, 최소내포디스크 문제의 핵심은 아니다.

의사 코드 ³

$(c,r)$ = welzl$\left( P, S \right)$

• Input: 주어진 점의 집합 $P = \left\{ p_{k} \right\}_{k=1}^{n} \subset \mathbb{R}^{d}$ 과 서포터의 후보 $S \subset P$ 를 받는다. 팁에서 언급했듯 $\left| S \right| \le d+1$ 이다.
• Output: $P$ 의 모든 점을 내포하는 가장 작은 디스크의 중심 $c$ 와 반지름 $r$ 의 튜플 $(c,r)$ 을 얻는다. 중심이 $c$ 고 반지름이 $r$ 인 클로즈드 볼을 $D = B \left[ c,r \right]$ 이라 나타내자.

$(c,r)$ = trivial$\left( S \right)$

• Input: $\left| S \right| \le d+1$ 인 점의 집합 $S \subset P$ 를 받는다.
• Output: $S$ 의 모든 점을 내포하는 가장 작은 디스크의 중심 $c$ 와 반지름 $r$ 의 튜플 $(c,r)$ 을 얻는다. welzl에 비해서 간단하다는 가정에 따라 trivial의 의사 코드는 따로 작성하지 않는다.

---

function welzl$\left( P, S \right)$
　　$S := \emptyset$
　　if $P = \emptyset$ or $\left| S \right| = d+1$ then
　　　　return trivial$\left( S \right)$
　　else
　　　　choose $p \in P$
　　　　$D := $ welzl$\left( P \setminus \left\{ p \right\}, S \right)$
　　　　if $p \in D$ then
　　　　　　return $D$
　　　　end if
　　end if
　　return welzl$\left( P \setminus \left\{ p \right\} , S \cup \left\{ p \right\} \right)$
end function

---

welzl은 재귀함수로 작성되기 때문에 실제 프로그램 상으로는 깊이 들어가서 trivial부터 계산하게 될 것이다. welzl의 의사 코드에서 등장하는 choose는 choose $x \in X$ 와 같은 꼴로 쓰여서 집합 $X$ 의 원소 $x$ 하나를 유니폼리 랜덤하게 뽑는 키워드^keyword다.

마지막에 welzl$\left( P \setminus \left\{ p \right\} , S \cup \left\{ p \right\} \right)$ 을 리턴하는 것 자체가 $P$ 에 있는 점을 하나씩 빼서 $S$ 에 넣어보며 서포트를 찾는 과정이라는 게 보인다면 이 알고리즘을 이해한 것이나 마찬가지다.

설명

최소 내포 디스크의 제약조건을 말로 그대로 풀어보자. $\left\| c - p_{k} \right\|_{2} \le r$ 을 만족하는 $c$ 와 $r$ 을 찾는다는 건 적어도 주어진 점들을 모두 감쌀^enclosing 수 있게끔 중심^centre $c$ 와 반지름^radius $r$ 을 찾는다는 것이다. 그러나 유클리드 공간은 무척 넓기 때문에 $c$ 가 어디든 $r$ 만 무작정 잡게 잡으면 이 제약조건은 무조건 만족시킬 수 있다. 당연히 우리의 관심사는 그러면서 $r$ 을 최소화하는 것, 다시 말해 주어진 점들을 감싸는 가장 작은 볼^ball을 찾는 것이다.

순화의 문제점

내포^enclosing는 수학 전반에서 널리 쓰이는 표현이 아니지만 발음 그대로 인클로징이라 하기에는 너무 길고 느낌이 안 와서 임의번역했다. 애초에 인클로징^enclosing부터가 바운딩^bounding을 압도하는 정도는 아니다. 또한 디스크^disk 역시 내부까지 포함하는 클로즈드 볼이라는 의미에서 쓰긴 했지만 실제 영어 표현으로는 그냥 볼^ball이나 스피어^sphere도 많이 쓴다. 단어와 번역 하나하나에 연연하지 말자.

역사

일찍이 라이문트 자이델^{raimund Seidel}에 의해 선형계획법에 기반한 해법이 알려져 있었다.

1991년 에모 벨츨^{emo Welzl}이 그의 논문에서 재귀적인^recursive 알고리즘을 제안했고 소위 말하는 SOTA^{state Of The Art}를 찍었다. 2022년 기준 아직까지 일반적인 최소내포디스크 문제에서는 이 벨츨의 알고리즘이 가장 뛰어난 것으로 알려져있고 이후의 많은 연구들은 이를 개선하는 방식으로 이루어져왔다.

1999년 베른트 가트너^{bernd Gärtner}는 벨츨의 알고리즘을 따르면서도 쿼드러틱 프로그래밍^{quadratic Programming}의 응용을 도입해 이를 개선했다⁴. 그의 코드는 C++로 작성되었으며 취리히 연방 공과대학교 웹사이트⁵에서 실제 구현을 볼 수 있다.

2003년 카스파 피셔^{kaspar Fischer}는 가트너와의 연구에서 선형계획법의 심플렉스 메소드에서 등장하는 브랜드 룰을 도입해 빠른 코드를 작성하고⁶ 2013년 토마스 랄슨^{thomas Larsson}은 근사적인 대신 속도와 강건성^robustness를 갖춘 방법을 제안했다.⁷

여기까지 소개된 연구들을 레퍼런스를 살펴보면 벨츨-가트너-피셔로 이어지는 큰 줄기를 확인할 수 있다.

응용

벨츨 알고리즘의 대표적인 응용은 체흐 컴플렉스를 구성하는 것이다.