# Optimizing Charging Pad Deployment by Applying a Quad-Tree Scheme
## 1 Introduction
However, in [6], [PERSON] et al. proposed three algorithms that only use sensor locations as potential deployment positions for the pads. Their simplified pad deployment problem is quite similar to the geometric connected dominating set, which is known to be NP-complete [6]. The major weakness of [PERSON] et al. 's best three schemes, which are based on graph theory, is that they only consider deploying a wireless charging pad at the locations of the wireless sensor nodes. Their schemes are limited and constrained because usually a pad can be deployed at every point in the deployed area. Moreover, the deployed pads suggested by these schemes may not be able to meet the connected requirements due to sparse environments. On the other hand, the remaining scheme in [6], which is based on geometry, is a blind strategy that does not consider the positions of the sensors at all. As a result, it always requires the deployment of more charging pads. In [13], [PERSON] et al. proposed a novel and adaptive pad deployment scheme that can adapt to arbitrary locations of the base station, arbitrary geographic distributions of sensor nodes, and arbitrary sizes of network areas. However, this scheme requires an appropriate determination of the number of clusters, which leads to a prolonged processing time. Based on above discussions, this work introduces a new scheme that utilizes the Quad-Tree concept [14; 15] to address the wireless charging pad deployment problem and reduce the number of deployed pads. The Quad-Tree concept represents spatial positions in a hierarchical manner [14; 15], allowing for the efficient exploration of suitable locations for pad deployment. By adopting the Quad-Tree concept, the new scheme not only overcomes the major limitation of previous approaches, which only deploy wireless charging pads at limited locations, but also efficiently identifies the appropriate locations from the infinite possible locations for pad deployment. Extensive simulations were conducted to illustrate the advantages of the proposed schemes by comparing them with different previous schemes on maps with varying sizes. For small maps, the previous schemes either struggled to find suitable pad configurations for certain maps or experienced prolonged processing times. In contrast, the proposed scheme encountered no issues with these small maps. Additionally, in terms of reducing the number of used pads, the proposed scheme slightly outperformed previous works. For medium-sized maps, the proposed schemes significantly outperformed all previous methods in reducing the number of required pads, with a maximum reduction of 12.37% and an average reduction of 9.59%. In the case of large maps, the proposed schemes surpassed all previous works, indicating that our approach is more suitable for large-scale network environments. Briefly, the contributions of this work are listed below:  
1. This work firstly applies the Quad-Tree concept to develop a new scheme in order to efficiently reduce the number of deployed wireless charging pads for the charging pad deployment problem. 2. If all spatial positions are expressed by the leaf nodes of a Quad-Tree, the execution time increases significantly. Therefore, it is necessary to analyze the Quad-Tree node splitting conditions to reduce the number of used Quad-Tree nodes. To further reduce the required execution time of the proposed schemes, we also designed some variations with different minimum units (as the splitting conditions in the Quad-Tree) to reduce the total execution time. 3. We also conducted extensive simulations to demonstrate the merits of the proposed schemes by comparing the proposed schemes with different previous methods on maps of different sizes. The rest of this work is organized as follows. Section 2 presents the related work. Section 3 introduces the proposed Quad-Tree schemes, followed by Section 4, which presents and discusses the simulation results by comparing the proposed schemes with previous methods. Finally, Section 5 concludes this work.