Topologically Aware Construction of Minimal Spanning Trees in Meshes
Masterarbeit, Bachelorarbeit
Most finite element methods can be related to some kind of mesh. In computational electromagnetism, the gradient can be associated with vertices and edges of the mesh. We can exploit this knowledge in simulations by identifying and using a spanning tree, i.e., a selection of #vertices−1 edges that connect all vertices. The vertices and edges are implicitly linked to the topology of the mesh. This can impact simulation as well because a tree might not provide enough information, which necessitates adding additional edges to obtain a belted tree. For the tree construction, the well-known Kruskal’s algorithm is a flexible and simple choice. It requires weights that are assigned to each edge and builds a minimal spanning tree, i.e., it tries to minimize the weights of the edges in the tree. This allows us to control the structure of the tree via specifying appropriate weights.