# A Clustering WSN Routing Protocol Based on k-d Tree Algorithm
## 3 Background and Preliminaries
### k-d Tree Algorithm  
Given the problem of two-dimensional rectangular range queries, a rectangle is divided into a smaller rectangle, which in turn is divided into another rectangle, and the process is repeated \(n\) times (depth), obtaining successive smaller areas. Within these areas (rectangles), we can locate a set of points that can be referenced as a unit, accessible via a route originated in a binary tree. Figure 4 shows the basic working idea of the k-d algorithm [46].  
Given \(P\) as the set of \(n\) points in the plane, we can assume as a principle that no two points share the same \((x,y)\) coordinates. There are no cases where two or more points are superimposed.  
**Definition 1**.: _In a two-dimensional rectangular range query in \(P\), we ask for the points in \(P\) inside the query rectangle \([x:x^{\prime}]*[y,y^{\prime}]\). A point \(p:=(p_{x},p_{y})\) is inside that rectangle if and only if:_  
\[p_{x}\in[x:x^{\prime}]\text{ and }p_{y}\in[y,y^{\prime}]. \tag{3}\]  
Figure 4: Visualization of the k-d tree algorithm.  
Definition 2: Recursive binary search tree for a set of points in one dimension is divided into two subsets of approximately the same size, based on the median of the set of points. In this way, the root contains two subsets distributed in two subtrees, where each subset of the subsets already created become subtrees that will be processed recursively.  
The procedure to build the k-d tree has two parameters: one set of points \(P\) and an integer value that represents the depth of the subtree root, as shown in Algorithm 1.  
```
0: A set of points \((x,y)\) named \(P\) and the tree depth value
0: The root of the k-d tree
1:function:\(build\_k\_d\_tree\left(P,depth\right)\)
2:if\(\left(P\) contains only one point\(\right)\)then
3:return the root with that point
4:elseif\(\left(depth\right)\) is an even number\(\right)then
5: divide the values of \(P\) into two subsets by using the median of the \(x\) coordinates of the \(P\) set. It generates two subsets:
6:if\(\left(P_{x_{i}}<\ median(x)\right)\)then
7:\(P_{x_{i}}^{1}:=subset_{left}\)
8:else
9:\(P_{x_{i}}^{2}:=subset_{right}\)
10:endif
11:else
12: divide the values of \(P\) into two subsets by using the median of the \(y\) coordinates of the \(P\) set. It generates two subsets:
13:endif
14:\(depth=depth+1\)
15:endfunction
```  
**Algorithm 1** k-d tree algorithm.  
For the function of the Algorithm 1:  
* Creates a root node with two subsets \(P_{(*)_{i}}^{1}\) for the left side of the tree and \(P_{(*)_{i}}^{2}\) for the right side of the tree.
* (\(*\)) is the subset of initial data where the partitioning of points will begin. In this algorithm, \(x\) is used for even depth values and \(y\) is used for odd values.
* Repeat steps 1 to 14 to create the branches of the tree, where the input parameter with the input data set is the subset \(P_{(*)_{i}}^{1,2}\).  
The time used in \(k\) groups of the kd-tree algorithm is \(O(k)\) for the depth of the tree and because \(P\) is a finite set each partition has a length in time of \(O(log(n))\), so the time total used in the algorithm is \(O(log(n)+k)\)[46].