Inferring local homology from sampled stratified spaces

被引:29
作者
Bendich, Paul
Cohen-Steiner, David
Edelsbrunner, Herbert
Harer, John
Morozov, Dmitriy
机构
来源
48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2007年
关键词
topological data analysis; local homology; persistence; stratified spaces; simplicial complexes; power diagrams; Delaunay triangulations; algorithms;
D O I
10.1109/FOCS.2007.45
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the reconstruction of a stratified space from a possibly noisy point sample. Specifically, we use the vineyard of the distance function restricted to a I-parameter family of neighborhoods of a point to assess the local homology of the stratified space at that point. We prove the correctness of this assessment under the assumption of a sufficiently dense sample. We also give an algorithm that constructs the vineyard and makes the local assessment in time at most cubic in the size of the Delaunay triangulation of the point sample.
引用
收藏
页码:536 / 546
页数:11
相关论文
共 28 条
  • [1] Surface reconstruction by Voronoi filtering
    Amenta, N
    Bern, M
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1999, 22 (04) : 481 - 504
  • [2] [Anonymous], 2007, Curve and Surface Reconstruction
  • [3] Laplacian eigenmaps for dimensionality reduction and data representation
    Belkin, M
    Niyogi, P
    [J]. NEURAL COMPUTATION, 2003, 15 (06) : 1373 - 1396
  • [4] BENDICH P, 2007, UNPUB PERSISTENT INT
  • [5] BREGLER C, 1995, FIFTH INTERNATIONAL CONFERENCE ON COMPUTER VISION, PROCEEDINGS, P494, DOI 10.1109/ICCV.1995.466899
  • [6] Chazal F., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry (SCG'06), P319, DOI 10.1145/1137856.1137904
  • [7] Cohen-Steiner D., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry (SCG'06), P119, DOI 10.1145/1137856.1137877
  • [8] Stability of persistence diagrams
    Cohen-Steiner, David
    Edelsbrunner, Herbert
    Harer, John
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2007, 37 (01) : 103 - 120
  • [9] COHENSTEINER D, IN PRESS FDN COMPUT
  • [10] 3-DIMENSIONAL ALPHA-SHAPES
    EDELSBRUNNER, H
    MUCKE, EP
    [J]. ACM TRANSACTIONS ON GRAPHICS, 1994, 13 (01): : 43 - 72