Reeb graph of the height function on a planar polygon

Authors

DOI:

https://doi.org/10.17721/1812-5409.2024/2.9

Keywords:

Morse function, topological structure, trapezoidal map, rectilinear graph

Abstract

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

2025-01-29

How to Cite

Tereshchenko, V., & Prishlyak, O. (2025). Reeb graph of the height function on a planar polygon. Bulletin of Taras Shevchenko National University of Kyiv. Physical and Mathematical Sciences, 79(2), 54–58. https://doi.org/10.17721/1812-5409.2024/2.9

Issue

Section

Computer Science and Informatics