nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Applications of Topological Graph Theory to 2-Manifold Learning

verfasst von : Tyrus Berry, Steven Schluchter

Erschienen in: Combinatorics, Graph Theory and Computing

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel A Matrix Criterion for Harmonic Morphisms of Graphs with Applications to Graph Products

Nächstes Kapitel 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

Titel: Applications of Topological Graph Theory to 2-Manifold Learning
verfasst von: Tyrus Berry
Steven Schluchter
Verlag: Springer Nature Switzerland
Buch: Combinatorics, Graph Theory and Computing
Print ISBN: 978-3-031-62165-9

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"