# 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
For a map of size \(m\) by \(m\), the maximum expanded level \(L\) is \(\log_{2}m+1\), and the maximum number of nodes that need to be processed is \(\frac{4^{L}-1}{4-1}\), which is proportional to \(m^{2}\). Therefore, the worst complexity of Quad-Tree construction (Algorithm 1) is \(\text{O}(nm^{2})\). ```
\(\textit{Tlist}:\text{Quad-Tree node list}\) \(\textit{Tlist}=\text{I}\); \(\textit{Tlist}(\text{I})=\text{BS}\); \(\textit{Tind}=\text{1}\); while\(\textit{Tlist}\) is not empty Split the \(\textit{Tlist}(\textit{Tind})\) node into four sub-blocks (\(\textit{Ult}\), \(\textit{UR}\), \(\textit{LL}\), and \(\textit{LR}\),) and calculate their attributes. If coverSets of \(\textit{Tlist}(\textit{Tind})\), \(\textit{UL}\), \(\textit{UR}\), \(\textit{LL}\), and \(\textit{LR}\) are all equal \(\textit{Tlist}(\textit{Tind})\_status=\text{1}\) \(\textit{Tind}=\textit{Tind}+\text{1}\) else Remove \(\textit{Tlist}(\textit{Tind})\) node from \(\textit{Tlist}\) Append UL, UR, LL and LR into \(\textit{Tlist}\)
```  
**Algorithm 1**Quad-Tree construction  
In sparser maps, there are more Quad-Tree nodes that do not require subdivision into the most basic grid points. To further reduce the likelihood of Quad-Tree nodes being  
Figure 4: All sensors within the radius \(D_{maxcharging}+dT\) (red circle) of the center position of the Quad-Tree node (red dot position) encompass all sensors that may be covered when the pad is placed at any position within this Quad-Tree node’s square area. subdivided downward, every time the placement position of a pad is determined, the sensors covered by it are excluded from consideration. As the number of sensors to be considered decreases, more Quad-Tree nodes do not require subdivision. In the methods proposed by [PERSON] et al. [6], the Minimum Set Cover (MSC) algorithm demonstrates good performance in terms of calculation speed and the number of pads used. Therefore, we propose an On-Demand Quad-Tree construction method combined with MSC, as illustrated in Figure 5. The overall procedure involves first executing the On-Demand Quad-Tree construction based on MSC (Algorithm 2) to configure pads at appropriate locations. Then, redundant pads are removed using Removing Redundant Pads (Algorithm 3), which internally calls Connectedness Checking (Algorithm 4) and Coverage Checking (Algorithm 5) to verify whether the connectedness and coverage constraints are satisfied. The details of Algorithms 2-5 are described below. ```
\(Tlist\): Quad-Tree node list \(Sset\): the set all sensors \(Tlist=[]\); \(Tlist(1)\)= BS; \(Tind=1\); \(pads=[\)BS\(]\); while\(Sset\) is not empty  Find the block \(m\) with the largest coverNum in \(Tlist\) if \(Tlist(m).status==0\)  Split the \(Tlist(Tind)\) node into four sub-blocks (\(UIL\), \(UR\), \(LL\), and \(LR\),) and calculate their attributes. if coverSets of \(Tlist(m)\), \(UIL\), \(UR\), \(LL\), and \(LR\) are all equal \(Tlist(m).status=1\) else Remove \(Tlist(m)\) node from \(Tlist\) Append \(UL\), \(UR\), \(LL\) and \(LR\) into \(Tlist\)
```  
**Algorithm 2** On-Demand Quad-Tree construction based on MSC  
Figure 5: The flowchart of the proposed method. ```
else if the distance between the center position of \(\mathit{Tlist}(m)\) and any pad in \(\mathit{pads}\) is less than \(\mathit{D}_{\mathit{maxpad}}\)  Append the center position of \(\mathit{Tlist}(m)\) into pads \(\mathit{Sset}=\mathit{Sset}-\mathit{Tlist}(m)\mathit{coverSet}\)  Remove \(\mathit{Tlist}(m)\mathit{coverSet}\) from the \(\mathit{coverSet}\) of all nodes in the \(\mathit{Tlist}\) else if \(\mathit{Tlist}(m)\) is not a basic grid point \(\mathit{Tlist}(m)\) is forcibly split into 4 child nodes and added to \(\mathit{Tlist}\) Remove \(\mathit{Tlist}(m)\) node from \(\mathit{Tlist}\) else Find the pad \(A\) which position is closest to \(\mathit{Tlist}(m)\) from pads  Place a pad \(B\) in the direction of pad A along \(\mathit{Tlist}(m)\). The distance between pad \(A\) and \(B\) is \(\mathit{D}_{\mathit{maxpad}}\)  Append pad \(B\) into \(\mathit{pads}\)
```  
**Algorithm 2**\(\mathit{Cont}\).