UDC 004.021+004.043+004.051

V. Tereshchenko
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine,
 vtereshch@gmail.com

A. Prishlyak
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine,
 prishlyak@knu.ua

M. Osiponok
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine,
 osipyonok@ukr.net

THE CONSTRUCTION OF EFFICIENT ALGORITHMS FOR ADDRESSING
CERTAIN COMPUTATIONAL GEOMETRY PROBLEMS
USING REEB GRAPHS

REFERENCES

• 1. Blum H. A transformation for extracting new descriptors of shape. Proc. Models for the Perception of Speech and Visual Form (11–14 November, 1964, Boston, USA). Cambridge, MA, 1967. P. 362–380.
• 2. Aichholzer O., Aurenhammer F., Alberts D., Grtner B. A novel type of skeleton for polygons. Journal of Universal Computer Science. 1995. Vol. 1, N 12. P. 752–761. https://doi.org/10.1007/978-3-642-80350-5_65.
• 3. Reeb G. Sur les points singuliers d’une forme de Pfaff completement integrable ou d’une fonction numerique. Comptes Rendus Acad. Sciences Paris. 1946. Vol. 222. P. 847–849.
• 4. Cole-McLaughlin K., Edelsbrunner H., Harrer J., Natarajan V., Pascucci V. Loops in Reeb graphs of 2-manifolds. Discrete and Computational Geometry. 2004. Vol. 32, N 2. P. 231–244. https://doi.org/10.1007/s00454-004-1122-6.
• 5. Pascucci V., Scorzelli G., Bremer P., Mascarenhas A. Robust on-line computation of Reeb graphs: Simplicity and speed. ACM Transactions on Graphics. 2007. Vol. 26, N 3. P. 58–66. https://doi.org/10.1145/1276377.1276449.
• 6. Prishlyak A. Conjugacy of Morse functions on surfaces with values on a straight line and circle. Ukrainian Mathematical Journal. 2000. Vol. 52, N 10. P. 1623–1627. https://doi.org/10.1023/A:1010461319703.
• 7. Hladysh B., Prishlyak A. Simple morse functions on an oriented surface with boundary. Журнал математичної фізики, аналізу, геометрії. 2019. Т. 15, № 3. С. 354–368. https://doi.org/10.15407/mag15.03.354.
• 8. Biasotti S., Giorgi D., Spagnuolo M., Falcidieno B. Reeb graphs for shape analysis and applications. Theoretical Computer Science. 2008. Vol. 392, N 1–3. P. 5–22. https://doi.org/10.1016/j.tcs.2007.10.018.
• 9. Tereshchenko V., Prishlyak O. Reeb graph of the height function on a planar polygon. Bulletin of Taras Shevchenko National University of Kyiv. Physical and Mathematical Sciences. 2025. Vol. 79, N 2. P. 54–58. https://doi.org/10.17721/1812-5409.2024/2.9.
• 10. Pryshliak O., Haieva K. Optimal Reeb graphs on two- and three-connected planar polygon. arXiv:2404.07193 [math.GT] 10 Apr 2024. https://doi.org/10.48550/arXiv.2404.07193.
• 11. Lee D.T., Preparata F.P. Location of a point in a planar subdivision and its applications. SIAM Journal on Computing. 1977. Vol. 6, Iss. 3. P. 594–606. https://doi.org/10.1137/0206043.
• 12. Aleardi L., Devillers O. Array-based compact data structures for triangulations: Practical solutions with theoretical guarantees. Journal of Computational Geometry. 2018. Vol. 9, N 1. P. 247–289. https://doi.org/10.20382/jocg.v9i1a8.
• 13. De Berg M., Cheong O., van Kreveld M., Overmars M. Computational geometry: Algorithms and applications. 3rd ed. Berlin; Heidelberg: Springer, 2008. 386 p.
• 14. Joe B., Simpson R.B. Corrections to Lee’s visibility polygon algorithm. BIT Numerical Mathematics. 1987. Vol. 27, N 4. P. 458–473. https://doi.org/10.1007/BF01937271.
• 15. O’Rourke J. Art gallery theorems and algorithms. New York: Oxford University Press, 1987. 282 p.
• 16. Boost.Container library. URL: https://boost.org/doc/libs/1_80_0/doc/html/container.html.
• 17. Geometric Tools: A collection of source code for computing in the fields of mathematics, geometry, graphics, image analysis and physics. URL: https://www.geometrictools.com.
• 18. Qt: Tools for each stage of software development lifecycle. URL: https://www.qt.io.
• 19. RPG: Random polygon generator. URL: https://github.com/cgalab/genpoly-rpg.
• 20. Auer T., Held M. Heuristics for the generation of random polygons. Proc. 8th Canadian Conference on Computational Geometry (12–15 August 1996, Ottawa, Canada). Carleton University Press, 1996. P. 38–43.
• 21. Osiponok M., Tereshchenko V. The “Divide and Conquer” technique to solve the Minimum Area Polygonalization problem. Proc. 2019 IEEE International Conference on Advanced Trends in Information Theory (18–20 December 2019, Kyiv, Ukraine). IEEE, 2019. P. 336–339. https://doi.org/10.1109/ATIT49449.2019.9030463.
• 22. CGAL: The computational geometry algorithms library. URL: https://www.cgal.org.
• 23. Earcut: A C++ port of earcut.js, a fast, header-only polygon triangulation library. URL: https://github.com/mapbox/earcut.hpp.
• 24. Eberly D. Triangulation by ear clipping. geometric tools. 18 November 2002. URL: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf.
• 25. PolyPartition: a lightweight C++ library for polygon partition and triangulation. URL: https://github.com/ivanfratric/polypartition.
• 26. Tereshchenko V.N., Anisimov A.V. Recursion and parallel algorithms in geometric modeling problems. Cybernetics and Systems Analysis. 2010. Vol. 46, N 2. P. 173–184. https://doi.org/10.1007/s10559-010-9196-z.