Top

Published in:

2024 | OriginalPaper | Chapter

Applications of Topological Graph Theory to 2-Manifold Learning

Authors : Tyrus Berry, Steven Schluchter

Published in: Combinatorics, Graph Theory and Computing

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We show how, given a sufficiently large point cloud sampled from an embedded 2-manifold in \(\mathbb {R}^n\), we may obtain a global representation of the embedded manifold as a cell complex with vertices given by a representative subset of the point cloud. We apply a known projection based approach (into approximations of tangent planes) from the studies of surface reconstruction and computer graphics, and we extend this with the application of techniques from topological graph theory for the purpose of topological identification of the sampled surface. We apply our methods to samples taken from orientable and nonorientable surfaces. Since our new approach is based on a cell complex rather than a triangulation, it does not derive from or apply Vornoi diagrams or any Delaunay structure.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Matrix Criterion for Harmonic Morphisms of Graphs with Applications to Graph Products

next chapter Properties of Sierpinski Triangle Graphs

Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation 6(15), 1373–1396 (2003)CrossRef

Coifman, R., Lafon, S.: Diffusion maps. Appl. Comp. Harmonic Anal. 5(21), 5–30 (2006)MathSciNetCrossRef

Singer, A.: From graph to manifold Laplacian: The convergence rate. Appl. Comp. Harmonic Anal. (21), 128–134 (2006)MathSciNetCrossRef

Carlsson, G.: Topology and data. Bull. Amer. Math. Soc. 2(46), 255–308 (2009)MathSciNetCrossRef

Edelsbrunner, H., Harer, J.: Computational Topology: an Introduction. Amer. Math. Soc., Providence, RI (2010)

Ghrist, R.: Barcodes: the persistent topology of data. Bull. Amer. Math. Soc. (45), 61–75 (2008)MathSciNetCrossRef

Dey, T.: Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press, New York, NY (2007)

Berger, M., Tagliasacchi, A., Seversky, L., Alliez, P., G. Guennebaud, J.L., Sharf, A., Silva, C.: A survey of surface reconstruction from point clouds. Computer Graphics Forum 36(1), 301–329 (2017) https://doi.org/10.1111/cgf.12802. https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.12802

Khatamian, A., Arabnia, H.: Survey on 3d surface reconstruction. J. Inf. Process Syst. 12(3), 338–357 (2016)

10.

Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., Taubin, G.: The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics 5(4), 349–359 (1999)CrossRef

11.

Gopi, M., Khrishnan, S.: A fast and efficient projection-based approach for surface reconstruction. High Performance Computer Graphics, Multimedia and Visualization 1(1), 1–12 (2000)

12.

Huang, J., Menq, C.H.: Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbitrary topology. Computer-Aided Design 34, 149–165 (2002)CrossRef

13.

Guerrero, P., Kleiman, Y., Ovsjanikov, M., Mitra, N.J.: Pcpnet learning local shape properties from raw point clouds. In: Computer Graphics Forum, vol. 37, pp. 75–85 (2018). Wiley Online Library

14.

Mérigot, Q., Ovsjanikov, M., Guibas, L.J.: Voronoi-based curvature and feature estimation from point clouds. IEEE Transactions on Visualization and Computer Graphics 17(6), 743–756 (2010)CrossRef

15.

Lin, H.-W., Tai, C.-L., Wang, G.-J.: A mesh reconstruction algorithm driven by an intrinsic property of a point cloud. Computer-Aided Design 36(1), 1–9 (2004)MathSciNetCrossRef

16.

Wang, W., Su, T., Liu, H., Li, X., Jia, Z., Zhou, L., Song, Z., Ding, M.: Surface reconstruction from unoriented point clouds by a new triangle selection strategy. Computers & Graphics 84, 144–159 (2019)CrossRef

17.

Di Angelo, L.,Di Stefano, P., Giaccari, L.: A new mesh-growing algorithm for fast surface reconstruction. Computer-Aided Design 43(6), 639–650 (2011)CrossRef

18.

Kuo, C.-C., Yau, H.-T.: A Delaunay-based region-growing approach to surface reconstruction from unorganized points. Computer-Aided Design 37(8), 825–835 (2005)CrossRef

19.

Marton, Z.C., Rusu, R.B., Beetz, M.: On fast surface reconstruction methods for large and noisy point clouds. In: 2009 IEEE International Conference on Robotics and Automation, pp. 3218–3223 (2009). IEEE

20.

Schöps, T., Sattler, T., Pollefeys, M.: Surfelmeshing: Online surfel-based mesh reconstruction. IEEE transactions on pattern analysis and machine intelligence 42(10), 2494–2507 (2019)CrossRef

21.

Adamson, A., Alexa, M.: Approximating bounded, nonorientable surfaces from points. In: Proceedings Shape Modeling Applications, 2004, pp. 243–252 (2004)

22.

Wang, J., Oliveira, M.M., Kaufman, A.E.: Reconstructing manifold and non-manifold surfaces from point clouds. In: VIS 05. IEEE Visualization, 2005, pp. 415–422 (2005)

23.

https://github.com/steveschluchter/rotation-systems-and-2-manifolds

24.

Berry, T., Harlim, J.: Iterated Diffusion Maps for Feature Identification. Appl. Comput. Harmon. Anal. 1(45), 84–119 (2018)MathSciNetCrossRef

25.

Munkres, J.: Topology, Second Edition. Prentice Hall, Upper Saddle River, NJ (2000)

26.

Gross, J., Tucker, T.: Topological Graph Theory. Wiley, New York, NY (1987)

27.

Archdeacon, D.: The medial graph and voltage-current duality. Discrete Math. (104), 111–141 (1992)MathSciNetCrossRef

28.

Schluchter, S.: Ordinary voltage graphs in pseudosurfaces and derived cellular homology with applications to graph embeddability. PhD thesis, The George Washington University (2014)

29.

Marsaglia, G.: Choosing a point from the surface of a sphere. Ann. Math. Stat. 45(2), 645–646 (1972)CrossRef

Title: Applications of Topological Graph Theory to 2-Manifold Learning
Authors: Tyrus Berry
Steven Schluchter
Publisher: Springer Nature Switzerland
Book: Combinatorics, Graph Theory and Computing
Print ISBN: 978-3-031-62165-9

Electronic ISBN: 978-3-031-62166-6

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-3-031-62166-6_20

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"