# Optimizing Charging Pad Deployment by Applying a Quad-Tree Scheme
## 3 Optimizing the Charging Pad Deployment Problem by Applying the Quad-Tree Scheme
### Proposed Method  
The previous approach only allows pads to be placed where sensors are located, which limits the available placement options. In sparse environments, this approach may fail to meet connectivity requirements. To address these limitations, the proposed approach divides the map into grid points where pads can be placed. However, sensor networks are typically deployed over large areas. For instance, in a 1 km by 1 km square area, dividing it into 1 m by 1 m square grid points would result in 1 million possible locations for deployed pads. Clearly, the solution space becomes too large and complex to find suitable and efficient pad placements. Therefore, this article proposes using the Quad-Tree scheme to represent spatial positions. Figure 2: Illustration of parameters \(a\) and \(b\). The listed edges represent the distances that satisfy the conditions, indicating feasible drone flight paths. The Quad-Tree represents spatial positions in a hierarchical manner. If all spatial positions, such as the grid points mentioned earlier, are represented by the leaf nodes of a Quad-Tree, the total number of Quad-Tree nodes that need to be processed will be much greater than the number of grid points. Therefore, it is necessary to analyze the conditions for splitting Quad-Tree nodes to reduce their number. In addition to leaf nodes, a Quad-Tree node represents a rectangular area. When information within the subdivided area is needed, the node is divided into four sub-areas. If the information obtained from a Quad-Tree node remains unchanged before and after subdivision, then further subdivision is unnecessary. Consider Figure 3 as an example. Assume the red point represents the center position of Quad-Tree node A, and the blue point represents the center position of its four child nodes B, C, D, and E. If the cover sets (the sets of sensors covered by a pad) resulting from placing a pad at the center position of nodes A to E are all equal, it indicates that Quad-Tree node A does not require further subdivision. This is because placing a pad at the center of node A already covers all sensors in the area. Therefore, in this article, the content of each Quad-Tree node is designed as listed in Table 2. \begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Meaning** \\ \hline cx, cy & The center position of a Quad-Tree node \\ size & The side length of the rectangular area represented by a Quad-Tree node \\ dT & Detailed description will be described later \\ coverSet & The set of sensors covered by the Quad-Tree node \\ coverNum & The number of sensors in _coverSet_ \\  & Whether the Quad-Tree node needs to be split again? \\ status & 0: Need to be split again. \\  & 1: No need to be split again. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The information stored in a Quad-Tree node. Figure 3: When the Quad-Tree node A covers the same sensors (red circle) as the ones within the range (blue circle) of its four child nodes B, C, D, and E, the Quad-Tree node A does not need to be subdivided into B, C, D, and E.  
In Figure 4 below, all sensors within the radius \(D_{maxcharging}\) of the blue dot can be covered by the pad placed at that position (i.e., the UAV can start from the dot position and reach any sensor within that range to charge, and then safely fly back). All sensors within the radius \(D_{maxcharging}+dT\) of the center position of the Quad-Tree node (represented by the red dot) include all sensors that may be covered when the pad is placed at any position within this square. The set of these sensors is the _coverSet_ of the Quad-Tree node. From Figure 2, we can observe that the value of \(dT\) is equal to \(\frac{\sqrt{2}}{2}\)_size_. Assuming that there are \(n\) sensors in the map, each Quad-Tree node's _coverSet_ needs to be checked every time it is expanded, and the complexity of checking the _coverSet_ is \(\text{O}(n)\).