Graph-based data structures for refinement and derefinement algorithms based on the longest edge bisection. Applications (Spanish text).

摘要

In the last years, mesh generation algorithms have been largely investigated. These algorithms are basic tools in numerical methods, as in the finite element method or in the piecewise linear approximation to a given function. The algorithms are also relevant in graphic engineering, computer graphics, surfaces and solid modeling, industrial design, visualization, CAD/CAM, etc. Furthermore, in an increasing way, the algorithms are getting used in Science and Technology Numerical Simulations; in this wide topic it is specially critical to provide algorithms with efficient performance in terms of time and space.; In the refinement and coarsening algorithms, an important point is to have a suitable data structure which makes it possible that the algorithms perform in an efficient way. This is due to the complexity of operations in the elements partitions which turn in a critical issue when the dimension increases and the number of elements grow rapidly.; This thesis investigates a new class of data structures which are based on the graph theory. The data structures are used to design new efficient versions of refinement and coarsening algorithms. We explore the main properties of the data structures in 2D. Moreover, a number of applications using the new version of the algorithms are provided.