# Algorithm Based on Morphological Operators for Shortness Path Planning
## 2 Morphological Search Framework
### Implementation Issues  
A discussion about the computational complexity of the two above algorithms is presented in the following paragraphs. The implementation is mainly affected by the expected order of connections in the graph \(G\). A graph is expressed as a finite list of nodes, and its analysis consists of a sequential process operating over one-to-one elements. The computational complexity is addressed in three main stages: (1) the morphological operators (covering dilation and frequency/weighted calculation); (2) the complexity in estimating the best path trajectory; and (3) the evaluation process for the selection of the best forward step from a given node. For (1), the complexity depends on the number of nodes \(|x^{*}|\) that denotes the cardinality of the \(x^{*}\) set and the expected order of all nodes involved in \(x^{*}\) expressed by the constant \(o^{*}\), which represents the structural element size of \(|\lambda|\). Then, the complexity is expressed as \(O(|x^{*}|\times o^{*}\times|\lambda|)\). The final complexity multiplies the previous complexity by a factor of \(k\), representing the worst number of dilations needed to cover the search space \(x^{*}\). In conclusion, the covering dilation complexity is \(O(|x^{*}|\times o^{*}\times|\lambda|\times k)\). The computational complexity of the frequency and weighted operators \(|\cdot|\) and \(||\cdot||\) operators is the same. In real scenarios, the covering and frequency/weighted operators might compute simultaneously, reducing the necessary computing time. In each iteration, the list of nodes for dilation might be computed separately because the dilation is performed independently; this makes it possible to segment them into \(m\) chunks (sublist) for the implementation of a parallel approach, reducing the final complexity by \(\frac{1}{m}\). Whenever the graph order is homogeneous across all elements, the computational complexity for a given dimensionality becomes \(O(n^{2m})\). The factor \(m\) denotes the space dimensionality. These spaces represent structures such as images, volumes, or any grid space. For (2), the loop to build the best trajectory consists of the backward analysis of the topological structure given by the frequency/weighted calculation. The minimum number of iterations to reach the goal \(D\) is given by \(|M_{x_{0}}|\); however, it might change according to how we implement the \(C\) criterion. Then, for practical purposes, the lower bound of the complexity is \(O(|M_{x_{0}}|)\) multiplied by the complexity of the \(C\) criterion. Finally, (3) refers to the criterion \(C\) for the step forward to the destination \(D\). This function requires a complexity of \(O(|N|)\) computations to determine the best choice. Then, the total complexity from stages (1) and (2) is \(O(|M_{x_{0}}|)\times O(|N|)\). In summary, the total complexity of Algorithm 1 is  
\[\underbrace{O(\tau|x^{*}|\times o^{*}\times|\lambda|\times k)}_{\text{ morphological operators}}+\underbrace{O(|M_{x_{0}}|)\times O(|N|)}_{\text{best path building}} \tag{9}\]  
where \(\tau\) is a constant that takes values of 2 or 3 if frequency dilation or weighted dilation is needed. In addition, the general search algorithm (see Algorithm 2) adds further complexity due to the loop (lines 3 to 9). Each iteration computes a coverage and its frequency. Hence, for each iteration, the maximum number of computed dilations depends on the \(k\) value. In fact, the complexity of computing a frequency and dilation is expressed as \(O(2\times|x^{*}|\times o^{*}\times|\lambda|\times k)\) for \(k\) iterations. Then, the loop requires evaluation \(1,\ldots,k\) times, and \(\Sigma=2\times|x^{*}|\times o^{*}\times|\lambda|\) denotes the iterations needed to perform the morphological process one time. The complexity is expressed as \(O(\Sigma\times 1+\ldots+\Sigma\times k)\) for the loop, which, after factorizing and rewriting the summation results, becomes \(O\Big{(}\Sigma\times\frac{(k+1)\times k}{2}\Big{)}\).