비에토리스-립스 복합체
Vietoris–Rips complex
위상에서는 비에토리스 콤플렉스(Vietoris complex) 또는 립스 콤플렉스(Rips complex)라고도 불리는 비에토리스-립스 콤플렉스는 일련의 지점들에서 거리로부터 위상학적 공간을 형성하는 방식이다.지름이 최대 Δ인 모든 유한한 점 집합에 대해 심플렉스(simplex)를 형성함으로써 어떠한 미터법 공간 M과 거리 Δ로부터도 정의할 수 있는 추상적인 단순화 콤플렉스다.즉, M의 유한 부분 집합의 계열로서, 여기서 k 포인트의 부분 집합은 (k - 1)차원 심플렉스 (2 포인트에 대한 에지, 3 포인트에 대한 삼각형, 4 포인트에 대한 사면체 등)를 형성하는 것으로 생각한다; 유한 세트 S가 S의 모든 포인트 쌍 사이의 거리가 최대 Δ인 특성을 가지고 있다면, S를 si로 포함한다.복합 단지의 복합체
역사
비에토리스-립스 콤플렉스는 원래 비에토리스 콤플렉스로 불렸는데, 레오폴드 비에토리스에게는 호몰로지 이론을 단순화 콤플렉스에서 미터법으로 확장하는 수단으로 도입했다.[1]엘리야후 립스가 쌍곡군 연구에 같은 콤플렉스를 적용한 후, 립스 콤플렉스라고 부르는 미하일 그로모프(1987)에 의해 그 사용이 대중화되었다.[2]'베토리스-립스 콤플렉스'라는 이름은 장클로드 하우스만(1995년) 때문이다.[3]
치치 콤플렉스와의 관계
비에토리스-립스 콤플렉스는 공 집합의 치치 콤플렉스(또는 신경)와 밀접하게 연관되어 있는데, 공 집합의 모든 유한 부분 집합에 대한 심플렉스(simplex)가 비어 있지 않다.지리적으로 볼록한 공간 Y에서 거리 Δ에 대한 모든 아공간 X y Y의 비토리스-립스 콤플렉스는 X의 점에 중심을 둔 Y의 반지름 Δ/2 공 집합의 치치 콤플렉스와 동일한 점과 가장자리를 가진다.그러나 X의 비토리스-립스 콤플렉스는 치치 콤플렉스와는 달리 X의 본질적 기하학적 기하학에만 의존하고 있으며, X가 어떤 더 큰 공간에 내재되어 있는 것은 아니다.
예를 들어, 각각이 서로 단위 거리에 있는 3개의 점으로 구성된 균일한 미터법 공간 M을3 고려해 보십시오.Δ = 1에 대한 M의3 Vietoris-Rips 콤플렉스는 M3 자체에 대한 삼각형을 포함하여3 M에 있는 점의 모든 부분 집합에 대한 심플렉스를 포함한다.만약 우리가3 M을 유클리드 평면에 등각 삼각형으로 내장한다면, M 지점의3 중심에 있는 반경 1/2볼의 체흐 콤플렉스는 베토리스-립스 콤플렉스의 다른 모든 단순함을 포함하지만, 이 삼각형을 포함하지는 않을 것이다. 세 공 모두에 포함된 평면의 점이 없기 때문이다.그러나 M의3 세 지점으로부터 각각 1/2 거리에 있는 네 번째 점을 포함하는 미터법 공간에 M을3 대신 내장한다면, 이 공간에 있는 반지름-1/2볼의 체치 콤플렉스는 삼각형을 포함할 것이다.따라서 M을3 중심으로 한 고정 반지름 공의 체흐 콤플렉스는 M이3 어떤 더 큰 공간에 내장될 수 있는지에 따라 달라지는 반면, 비에토리스-립스 콤플렉스는 변함이 없다.
어떤 미터법 공간 X가 주입식 미터법 공간 Y에 내장되어 있다면, 거리 Δ와 X에 대한 비에토리스-립스 콤플렉스는 Y의 X 점을 중심으로 반경 Δ/2의 공의 치치 콤플렉스와 일치한다.따라서 미터법 공간 M의 베토리스-립스 콤플렉스는 M의 좁은 범위에 있는 공의 체흐 콤플렉스와 같다.
단위 디스크 그래프 및 클라이크 복합체와의 관계
Δ = 1에 대한 Vietoris-Rips 콤플렉스는 주어진 메트릭 공간에서 단위 거리 이하에 있는 모든 점 쌍에 대한 에지를 포함한다.이와 같이, 그것의 1-골격은 그것의 점들의 단위 디스크 그래프이다.단위 디스크 그래프의 모든 클라이크에 대한 심플렉스(Simplex)를 포함하고 있어 단위 디스크 그래프의 클라이크 콤플렉스(clique complex) 또는 플래그 콤플렉스(plag complex)이다.[4]보다 일반적으로 그래프 G의 클라이크 콤플렉스는 G의 정점을 가리키고 G에서 가장 짧은 경로의 길이를 거리만큼 갖는 메트릭 공간을 위한 베토리스-립스 콤플렉스다.
기타 결과
M이 닫힌 리만 다지관인 경우, M의 베토리스-립스 콤플렉스 또는 M에 충분히 가까운 공간의 Δ의 충분한 작은 값은 M 그 자체와 동등한 호모토피이다.[5]
챔버스, Erickson & Worah(2008)는 유클리드 평면에 설정된 유한 지점의 립스 콤플렉스에서 주어진 사이클이 수축 가능한지 여부를 결정하기 위한 효율적인 알고리즘을 설명한다.
적용들
유닛 디스크 그래프와 마찬가지로, 컴퓨터 공학에 베토리스-립스 콤플렉스가 적용되어 애드혹 무선 통신 네트워크의 토폴로지를 모델링하고 있다.이 애플리케이션에서 베토리스-립스 콤플렉스의 한 가지 장점은 정확한 물리적 위치를 유추할 필요 없이 통신 노드 사이의 거리에서만 결정할 수 있다는 것이다.단점은 치치 콤플렉스와 달리 베토리스-립스 콤플렉스는 통신 커버리지의 격차에 대한 정보를 직접 제공하지 않지만, Δ의 다른 값을 위해 두 베토리스-립스 콤플렉스 사이에 있는 치치 콤플렉스를 샌드위치시켜 이 결함을 개선할 수 있다는 점이다.[6]Vietoris-Rips 단지의 구현은 TDAstats R 패키지에서 확인할 수 있다.[7]
베토리스-립스 콤플렉스는 디지털 이미지 데이터의 형상 추출에도 적용되었으며, 이 어플리케이션에서는 포인트가 낮은 이미지 특징을 나타내는 고차원 미터법으로 콤플렉스를 구축하였다.[8]
메모들
참조
- Carlsson, Erik; Carlsson, Gunnar; de Silva, Vin (2006), "An algebraic topological method for feature identification" (PDF), International Journal of Computational Geometry and Applications, 16 (4): 291–314, doi:10.1142/S021819590600204X, archived from the original (PDF) on 2019-03-04.
- Chambers, Erin W.; Erickson, Jeff; Worah, Pratik (2008), "Testing contractibility in planar Rips complexes", Proceedings of the 24th Annual ACM Symposium on Computational Geometry, pp. 251–259, CiteSeerX 10.1.1.296.6424, doi:10.1145/1377676.1377721.
- Chazal, Frédéric; Oudot, Steve (2008), "Towards Persistence-Based Reconstruction in Euclidean Spaces", ACM Symposium on Computational Geometry: 232–241, arXiv:0712.2638, doi:10.1145/1377676.1377719, ISBN 978-1-60558-071-5.
- de Silva, Vin; Ghrist, Robert (2006), "Coordinate-free coverage in sensor networks with controlled boundaries via homology", The International Journal of Robotics Research, 25 (12): 1205–1222, doi:10.1177/0278364906072252.
- Gromov, Mikhail (1987), "Hyperbolic groups", Essays in group theory, Mathematical Sciences Research Institute Publications, vol. 8, Springer-Verlag, pp. 75–263.
- Hausmann, Jean-Claude (1995), "On the Vietoris–Rips complexes and a cohomology theory for metric spaces", Prospects in Topology: Proceedings of a conference in honour of William Browder, Annals of Mathematics Studies, vol. 138, Princeton University Press, pp. 175–188, MR 1368659.
- Latschev, Janko (2001), "Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold", Archiv der Mathematik, 77 (6): 522–528, doi:10.1007/PL00000526, MR 1879057.
- Lefschetz, Solomon (1942), Algebraic Topology, New York: Amer. Math. Soc., p. 271, MR 0007093.
- Muhammad, A.; Jadbabaie, A. (2007), "Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians" (PDF), in Broch, Oliver (ed.), Robotics: Science and Systems, MIT Press.
- Reitberger, Heinrich (2002), "Leopold Vietoris (1891–2002)" (PDF), Notices of the American Mathematical Society, 49 (20).
- Vietoris, Leopold (1927), "Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen", Mathematische Annalen, 97 (1): 454–472, doi:10.1007/BF01447877.
- Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018), "TDAstats: R pipeline for computing persistent homology in topological data analysis", Journal of Open Source Software, 3 (28): 860, doi:10.21105/joss.00860
