Constructing Efficient Algorithms for Solving Certain Computational Geometry Problems Using Reeb Graphs
摘要
The properties of the Reeb graph and the algorithm for its construction based on the sweep line technique are investigated. The potential of using the Reeb graph to develop efficient algorithms for solving computational geometry problems is evaluated. An algorithm for decomposing a planar polygon into monotone polygons with simultaneous triangulation, based on the properties of the Reeb graph, has been constructed, and its efficiency has been analyzed relative to other triangulation algorithms.