4.8.3 Algorithmic Complexity

The setup of the graph requires a sequential traversal over the H-RLE data structure. A first order finite difference stencil is used to enable fast access to neighbor grid points. Hence, the neighbor grid points of the first point of each segment can be tested for connectivity in constant time. As a consequence, the overall complexity required to set up the reduced graph exhibits a linear scaling with the number of defined grid points ${{N}_\text{D}}$ . For the size of the reduced graph ${{N}_\text{E}}+{{N}_\text{V}}\leq{\mathcal{O}}({{N}_\text{D}})$ holds, since each segment in the H-RLE data structure leads to the insertion of, at most, one vertex and $2{D}$ edges, if ${D}$ is the number of dimensions. As previously mentioned, the connected components of a graph can be obtained with linear complexity, which leads to an overall algorithmic complexity of ${\mathcal{O}}({{N}_\text{D}})$ .

The memory requirements are also optimal. For each segment of the H-RLE data structure a reference of the corresponding vertex must be stored. The memory requirements for the reduced graph can usually be neglected, because, in practice, the number of vertices is much smaller than the number of segments.