Reeb graph of the height function on a planar polygon
DOI:
https://doi.org/10.17721/1812-5409.2024/2.9Keywords:
Morse function, topological structure, trapezoidal map, rectilinear graphAbstract
Height functions, which are Morse functions of the general position, are often used when studying the structure of manifolds. The structure of such functions is described using the Reeb graph. On two-dimensional oriented closed manifolds, as well as on compact domains with a smooth boundary, the Reeb graph is a complete topological invariant of a simple Morse function. Its vertices have degree 1 if the vertex corresponds to a local extremum, or 3 if the vertex corresponds to a saddle critical point. For the height function on a polygon, we consider a Reeb graph whose vertices coincide with the vertices of the polygon. In this case, in addition to vertices of degrees 1 and 3, the Reeb graph will also have vertices of degree 2, which correspond to the regular vertices of the polygon. We show that the Reeb graph of a polygon can be constructed in a time no less than O(n log n), which is the best possible for many computational geometry problems. In addition, the Reeb graph can be embedded as a rectilinear graph in a polygon. This allows you to construct a division of a polygon into monotone polygons with their subsequent triangulation. We have also established the connection between the Reeb graph of the polygon and the Reeb graph of the height function on the smoothed axis 3D thickening, which opens up the possibility of using these structures to build the skeleton of 3D models with its further use in computer graphics. We give an example of constructing a Reeb graph using the process of planar sweeping with a straight line and subsequent triangulation of a polygon. The obtained results can also be used to study the properties of Reeb graphs of combinations of polygons in three-dimensional space. It is also promising to find all possible Reeb graphs of polygons with a small number of vertices.
Pages of the article in the issue: 54 - 58
Language of the article: English
References
Cole-McLaughlin K., Edelsbrunner H., Harrer J. , Natarajan V. , Pascucci V. (2004) Loops in Reeb graphs of 2-manifolds, Discrete and Computational Geometry 32, 231-24 http://www.pascucci.org/pdf-papers/reeb-loops.pdf
Hladysh B., Prishlyak A. (2019) Simple morse functions on an oriented surface with boundary. Journal of Mathematical Physics, Analysis, Geometry, 15(3), 354–368 https://doi.org/10.15407/mag15.03.354
Hladysh B., Prishlyak A. (2020) Deformations in the General Position of the Optimal Functions on Oriented Surfaces with Boundary Ukrainian Mathematical Journal, 71(8), 1173–1185 https://umj.imath.kiev.ua/index.php/umj/article/view/1495
Hladysh B, Prishlyak A. (2016) Functions with Nondegenerate Critical Points on the Boundary of the Surface . Ukrainian Mathematical Journal , 68(1), 29–40 https://umj.imath.kiev.ua/index.php/umj/article/view/1819
Kravchenko A., Maksymenko, S. (2020) Automorphisms of Kronrod–Reeb graphs of Morse functions on compact surfaces. European Journal of Mathematics , 6(1), 114–131 https://doi.org/10.1007/s40879-019-00379-8
Maksymenko S. (2020) Deformations of functions on surfaces by isotopic to the identity diffeomorphisms. Topology and its Applications, 282, 107312 https://doi.org/10.1016/j.topol.2020.10731
Polulyakh E. (2016) Kronrod–Reeb Graphs of Functions on Noncompact Two-Dimensional Surfaces. II, Ukrainian Mathematical Journal , 67(10), 1572–1583 https://umj.imath.kiev.ua/index.php/umj/article/view/1990
Preparata F., Shamos M. (1985). Computational Geometry: An Introduction. Springer. https://www.cs.kent.edu/~dragan/CG/CG-Book.pdf
Prishlyak A., Loseva M. (2020) Topology of optimal flows with collective dynamics on closed orientable surfaces Proceedings of the International Geometry Center, 13(2), 50–67 https://doi.org/10.15673/tmgc.v13i2.173
Prishlyak A. (2000) Conjugacy of Morse functions on surfaces with values on a straight line and circle. Ukrainian Mathematical Journal , 52(10), 1623–1627 https://link.springer.com/article/10.1023/A:101046131970
Prishlyak A. (2002) Topological equivalence of Morse-Smale vector fields with beh2 on three-dimensional manifolds. Ukrainian Mathematical Journal, 54(4), 603–616 https://umj.imath.kiev.ua/index.php/umj/article/view/4087
Reeb G. (1954) Sur les points singulies d’une forme de Pfaff completion integrable ou d'une fonction numerique. Comp. Rend. Hebdomadaires Seaces Acad. Sci. 222, 847-849.
Tereshchenko, V.,Tereshchenko, Y. (2017). Triangulating a region between arbitrary polygons. International Journal of Computing, 16(3), 160–165. https://www.computingonline.net/computing/article/viewFile/899/798
Tereshchenko, V. (2009) One tool for building visual models. CSSim 2009 - 1st International Conference on Computational Intelligence, Modelling, and Simulation, 2009, 59–62. https://doi.org/10.1109/CSSim.2009.55
Tereshchenko, V.,Pilipenko, S.,Fisunenko, A.(2013) Domain triangulation between convex polytopes. Procedia Computer Science, 2013, 18, 2500–2503 https://doi.org/10.1016/j.procs.2013.05.428
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Vasyl Tereshchenko, Oleksandr Prishlyak

This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).