# A Relative Coordinate-Based Topology Shaping Method for UAV Swarm with Low Computational Complexity
## 3 The Construction of Initial and Target Topology Coordinate Systems  
The Multidimensional Scaling (MDS) algorithm is one of the dimensionality reduction techniques that transforms multidimensional data into a lower-dimensional space while retaining the inherent information [37; 38; 39]. The MDS algorithm uses distance as a criterion while maintaining the exact distances between the original points and the dimension-reduced points, thus can be used to establish the coordinate system according to the inter-distance information of nodes. From Equation (1), it can be found that \(\delta_{ij}=\delta_{ji}\), \(\delta_{ii}=0\), for all \(i,j=1,2,\ldots,N\). The distance matrix of initial topology is a symmetric matrix, which consists of \(\delta_{ij}\) and expressed as  
\[\Delta=[\delta_{ij}]_{N\times N}=\left[ \begin{array}{cccc}\delta_{11}& \delta_{12}&\cdots&\delta_{1N}\\ \delta_{21}&\delta_{22}&\cdots&\delta_{2N}\\ \vdots&\vdots&\ddots&\vdots\\ \delta_{N1}&\delta_{N2}&\cdots&\delta_{NN}\\ \end{array} \right]. \tag{7}\]  
According to \(\Delta\), the square of distance \(\delta_{ij}^{2}\) is calculated by  
\[\delta_{ij}^{2}=\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|^{2}=\left\| \mathbf{x}_{i}\right\|^{2}+\left\|\mathbf{x}_{j}\right\|^{2}-2\mathbf{x}_{i}^ {T}\mathbf{x}_{j}. \tag{8}\]  
In general, the geometric center of the swarm system is selected as the coordinate origin, which means  
\[\sum_{i}\mathbf{x}_{i}=0. \tag{9}\]Thus, \(\delta_{ij}^{2}\) can be obtained as follows:  
\[\sum_{j}\delta_{ij}^{2} =N\|\mathbf{x}_{i}\|^{2}+\sum_{j}\bigl{\|}\mathbf{x}_{j}\bigr{\|}^{2 }-2\mathbf{x}_{i}^{T}\sum_{j}\mathbf{x}_{j}\] \[=N\|\mathbf{x}_{i}\|^{2}+\sum_{j}\bigl{\|}\mathbf{x}_{j}\bigr{\|}^{2}, \tag{10}\] \[\sum_{i}\delta_{ij}^{2} =N\bigl{\|}\mathbf{x}_{j}\bigr{\|}^{2}+\sum_{i}\bigl{\|}\mathbf{x }_{i}\bigr{\|}^{2}-2\mathbf{x}_{j}^{T}\sum_{i}\mathbf{x}_{i}\] \[=N\bigl{\|}\mathbf{x}_{j}\bigr{\|}^{2}+\sum_{i}\bigl{\|}\mathbf{x }_{i}\bigr{\|}^{2},\] (11) \[\sum_{ij}\delta_{ij}^{2} =N\sum_{i}\bigl{\|}\mathbf{x}_{i}\bigr{\|}^{2}+N\sum_{j}\bigl{\|} \mathbf{x}_{j}\bigr{\|}^{2}. \tag{12}\]  
Based on Equations (10)-(12), we obtain  
\[\|\mathbf{x}_{i}\|^{2}+\bigl{\|}\mathbf{x}_{j}\bigr{\|}^{2}=\frac{1}{N}\sum_{ i}\delta_{ij}^{2}+\frac{1}{N}\sum_{j}\delta_{ij}^{2}-\frac{1}{N^{2}}\sum_{i,j} \delta_{ij}^{2} \tag{13}\]  
For the node relative coordinate \(\mathbf{x}_{i},i=1,2,3,\cdots,N\), the initial relative coordinate matrix can be expressed by  
\[\mathbf{X}=\left[ \begin{array}{c}\mathbf{x}_{1}^{T}\\ \mathbf{x}_{2}^{T}\\ \vdots\\ \mathbf{x}_{N}^{T}\end{array} \right]. \tag{14}\]  
Defining a matrix  
\[\mathbf{Y}=\mathbf{X}\mathbf{X}^{T}, \tag{15}\]  
then for any \(y_{ij},\ i,j=1,2,3\cdots,N\), in \(\mathbf{Y}\),  
\[y_{ij}=\mathbf{x}_{i}^{T}\mathbf{x}_{j}. \tag{16}\]  
According to Equation (8), \(y_{ij}\) can be derived by  
\[y_{ij}=-\frac{1}{2}\Bigl{(}\delta_{ij}^{2}-\|\mathbf{x}_{i}\|^{2}-\bigl{\|} \mathbf{x}_{j}\bigr{\|}^{2}\Bigr{)}. \tag{17}\]  
Combing Equations (13) and (17), \(y_{ij}\) can be expressed by  
\[y_{ij}=-\frac{1}{2}\Biggl{[}\delta_{ij}^{2}-\frac{1}{N}\sum_{i}\delta_{ij}^{2 }-\frac{1}{N}\sum_{j}\delta_{ij}^{2}+\frac{1}{N^{2}}\sum_{i,j}\delta_{ij}^{2} \Biggr{]}. \tag{18}\]  
Based on Equation (18), the matrix \(\mathbf{Y}\) can be obtained. By performing a eigen-decomposition [40], \(\mathbf{Y}\) can be decomposed by  
\[\mathbf{Y}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{T}=\mathbf{U}\sqrt{\mathbf{ \Lambda}}\bigl{(}\mathbf{U}\sqrt{\mathbf{\Lambda}}\bigr{)}^{T}, \tag{19}\]  
where \(\mathbf{U}\) is the matrix composed of the three eigenvectors of \(\mathbf{Y}\), and \(\mathbf{\Lambda}\) is the diagonal matrix composed of the three largest eigenvalues of \(\mathbf{Y}\).