비에토리스-립스 컴플렉스의 정의
정의 1 2
쉬운 정의
유클리드 공간 $\left( \mathbb{R}^{d} , \left\| \cdot \right\|_{2} \right)$ 와 양수 $\varepsilon > 0$ 이 주어져 있다고 하자. 유한집합 $S \subset \mathbb{R}^{d}$ 에 대해 다음의 두 조건을 만족하는 심플리셜 컴플렉스 $\text{VR}_{\varepsilon} (S)$ 를 비에토리스-립스 컴플렉스vietoris-Rips Complex라 한다.
- (i): $S$ 를 버텍스의 집합으로 가진다.
- (ii): $k$-심플렉스 $\left[ v_{0} , v_{1} , \cdots, v_{k} \right]$ 가 $\text{VR}_{\varepsilon} (S)$ 에 속한다는 것은 모든 $0 \le i,j \le k$ 에 대해 다음이 성립하는 것과 동치다. $$ \left\| v_{i} - v_{j} \right\|_{2} \le 2 \varepsilon $$
어려운 정의
거리공간 $\left( X, d \right)$ 와 양수 $\varepsilon > 0$ 이 주어져 있다고 하자. 유한집합 $S \subset X$ 에 대해 다음과 같이 정의된 추상 심플리셜 컴플렉스 $\text{VR}_{\varepsilon} (S)$ 을 비에토리스-립스 컴플렉스vietoris-Rips Complex라 한다. $$ \text{VR}_{\varepsilon} (S) := \left\{ \sigma \subset S : \diam \sigma \le 2 \varepsilon \right\} $$ 여기서 $\diam$ 는 지름diameter로써, 다음과 같이 주어진 집합 $\sigma \subset X$ 의 모든 점끼리의 거리의 슈프리멈으로써 정의된다. $$ \diam \sigma := \sup_{x_{1} , x_{2} \in \sigma} d \left( x_{1} , x_{2} \right) $$
설명
비에토리스-립스 컴플렉스vietoris-Rips Complex는 가끔 줄여서 그냥 VR 컴플렉스나 립스 컴플렉스라 불리기도 한다.
조금 다르게 적히긴 했지만, 쉬운 정의가 되었든 어려운 정의가 되었든 핵심은 심플렉스가 되기 위한 조건이 거기에 포함된 모든 점들의 거리가 $2 \varepsilon$ 이하라는 것이다. 이를 그림으로 그려보면 다음과 같이 $0$-심플렉스인 버텍스들이 중심이고 반지름 $\varepsilon$ 인 볼들을 생각했을 때 두 볼끼리 닿는 것을 기준으로 $1$-심플렉스를 만들고, 세 버텍스가 $1$-심플렉스로 이어져 있으면 $2$-심플렉스를 만드는 식으로 VR 컴플렉스를 구성할 수 있다.
비에토리스-립스 컴플렉스와 체흐 컴플렉스의 차이
비에토리스-립스 컴플렉스: $$\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$ 보다 긴지 짧은지 알 수가 없기 때문이다. 이를 극복하고 체흐 컴플렉스를 구축하기 위한 방법 중 하나로 벨츨 알고리즘 등으로 최소내포디스크를 찾는 방식을 고려해볼 수 있는데, 그 한 번 한 번의 계산들이 꽤 비싼데다가 그 비싼 계산을 가능한 모든 점의 조합에 대해 반복해야한다.