📂위상데이터분석

체흐 컴플렉스의 정의

정의 ^{1 2}

거리공간 $\left( X, d \right)$ 와 양수 $\varepsilon > 0$ 이 주어져 있다고 하자. 유한집합 $S \subset X$ 에 대해 다음과 같이 정의된 추상 심플리셜 컴플렉스 $\check{C}_{\varepsilon} (S)$ 을 체흐 컴플렉스^{Čech Complex}라 한다. $$\check{C}_{\varepsilon} (S) := \left\{ \sigma \subset S : \bigcap_{x \in \sigma} B_{d} \left( x ; \varepsilon \right) \ne \emptyset \right\}$$

여기서 $B_{d} (c; r)$ 은 주어진 거리공간에서 중심^centre이 $c \in X$ 고 반경^radius이 $r \in \mathbb{R}$ 인 오픈 볼이다. $$B_{d} \left( c ; r \right) := \left\{ x \in X : d (c,x) < r \right\}$$

설명

정의가 조금 지나치게 어렵게 적혀 있는데, 사실 유클리드 공간 $\left( \mathbb{R}^{d} , \left\| \cdot \right\|_{2} \right)$ 에서 생각해보면 그냥 볼이 다 겹쳐있을 때만 심플렉스로 인정하는 심플리셜 컴플렉스라 생각하면 편하다. 수식만 붙잡고 있지 말고 비에토리스-립스 컴플렉스와 어떤 점이 다른지만 살펴보면 한 번에 이해가 된다.

비에토리스-립스 컴플렉스와 체흐 컴플렉스의 차이

비에토리스-립스 컴플렉스: $$\text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\}$$

체흐 컴플렉스: $$\check{C}_{\varepsilon} (S) := \left\{ \sigma \subset S : \bigcap_{x \in \sigma} B_{d} \left( x ; \varepsilon \right) \ne \emptyset \right\}$$

다음 그림은 같은 데이터에 대해 비에토리스-립스 컴플렉스와 체크 컴플렉스를 비교한 것이다. 위는 $\text{VR}_{\varepsilon}$, 아래는 $\check{C}_{\varepsilon}$ 다.

• 비에토리스-립스는 $k$-심플렉스를 포함하는 조건으로써 그 페이스^face인 $k-1$-심플렉스가 존재하는 것만을 요구한다. 예시에서는 $1$-심플렉스인 $AB$, $BC$, $CA$ 가 존재하므로 $2$-심플렉스인 $ABC$ 가 포함된다.
• 그에 반해 체흐 컴플렉스는 그 페이스들을 포함하는 것은 물론, $ABC$ 자체도 그 볼들이 한 점으로 묶여야만한다. 이는 체흐 컴플렉스를 구축하는 조건이 비에토리스-립스 컴플렉스를 구축하기보다 까다롭다는 것을 의미하며, 이에 따라 다음을 알 수 있다. $$\check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon}$$ 더 나아가, 다음의 팩트가 알려져있다. $$\check{C}_{\varepsilon} \subset \text{VR}_{\varepsilon} \subset \check{C}_{2 \varepsilon}$$

정의로써 짐작할 수 있는 것은 아마도 체흐 컴플렉스가 비에토리스-립스 컴플렉스에 비해 조금 더 많은 정보를 가질 수 있다는 점이다. $\text{VR}_{\varepsilon}$ 은 $k \le n$ 개의 점이 주어졌을 때 이들이 서로 연결되어있기만 하면 얄짤없이 그 $k-1$-심플렉스가 존재한다고 말한다. 말하자면 심플렉스의 존재성과 그 모든 페이스들의 존재성 사이에 차이가 없다. 예로써 $2$-심플렉스인 $ABC$ 가 존재한다는 말이나 $1$-심플렉스인 $AB$, $BC$, $CA$ 가 존재한다는 말은 그냥 정확히 동치고, 조금 과감하게 말해서 둘 중 하나를 안다면 솔직히 나머지 하나는 무의미한 정보다. 반면 $\check{C}_{\varepsilon}$ 은 $AB$, $BC$, $CA$ 가 존재한다는 것만으로 $ABC$ 의 존재성을 장담할 수 없고 별도의 확인을 거쳐야한다. 이러한 점에서 체흐 컴플렉스는 비에토리스-립스 컴플렉스에 비해 데이터를 조금 더 디테일하게 바라보고 있는 것이라 기대할 수 있는 것이다.

한편 실제 계산의 측면에서는 비에토리스-립스 컴플렉스를 구축하는 계산 비용이 압도적으로 저렴하다. 그도 그럴 것이, 단순히 고정됨 점과 점 사이의 거리를 계산하는 $\text{VR}_{\varepsilon}$ 과 달리 $\check{C}_{\varepsilon}$ 은 점들의 볼들이 어디서 만나는지도 알 수 없으며 만난다고 할지라도 그것이 $\varepsilon$ 보다 긴지 짧은지 알 수가 없기 때문이다. 이를 극복하고 체흐 컴플렉스를 구축하기 위한 방법 중 하나로 벨츨 알고리즘 등으로 최소내포디스크를 찾는 방식을 고려해볼 수 있는데, 그 한 번 한 번의 계산들이 꽤 비싼데다가 그 비싼 계산을 가능한 모든 점의 조합에 대해 반복해야한다.