# Drone Deployment Algorithms for Effective Communication Establishment in Disaster Affected Areas
## 3 Proposed Methods
### Region Filling
#### 3.4.6 The Region-Filling Algorithm
\begin{tabular}{l l} \hline
28: & \(\mathit{FillAlongXaxis}(d)\) \\
29: & \(\mathit{FillAlongYaxis}(d)\) \\
30: & **while**_true_**do** \\
31: & \(d_{1}\gets d.north,d_{2}\gets d.east\) \\
32: & **if**\(d_{1}\) _or_\(d_{2}\)_is not defined_**then** \\
33: & **break** \\
34: & **endif** \\
35: & \((x_{1},y_{1})\leftarrow(x_{2},y_{2})\leftarrow\mathit{not}\mathit{defined}\) \\
36: & **if**\(\sqrt{(d_{1}.x-d_{2}.x)^{2}+(d_{1}.y-d_{2}.y)^{2}}\leq d_{1}.r+d_{2}.r\)**then** \\
37: & \(d_{3}\leftarrow\mathit{TwoNeighours}(d_{1},d_{2})\) \\
38: & \((x_{1},y_{1})\leftarrow\mathit{ArbitraryDistant}(d_{1}.x,d_{1}.y,d_{2}.x,d_{2 }.y,d_{1}.r,d_{2}.r,0)\) \\
39: & **else** \\
40: & \(d_{3}\leftarrow\mathit{ThreeNeighours}(d_{1},d,d_{2})\) \\
41: & **if**\(d_{3}\) _is not defined_**then** \\
42: & \(d_{4}\leftarrow\mathit{TwoNeighours}(d_{1},d_{2})\) \\
43: & \(d_{5}\leftarrow\mathit{TwoNeighours}(d,d_{2})\) \\
44: & \(D\leftarrow D\cup\{d_{4},d_{5}\}\) \\
45: & \(\mathit{InnerXDirectionFilling}(d_{5})\) \\
46: & \(\mathit{InnerYDirectionFilling}(d_{4})\) \\
47: & **continue** \\
48: & **else** \\
49: & \((x_{1},y_{1})\leftarrow\mathit{ArbitraryDistant}(d_{1}.x,d_{1}.y,d.x,d.y,d_{1 }.r,d.r,0)\) \\
50: & \((x_{2},y_{2})\leftarrow\mathit{ArbitraryDistant}(d.x,d.y,d_{2}.x,d_{2}.y,d.r,d _{2}.r,0)\) \\
51: & **endif** \\
52: & **endif** \\
53: & **if**\((d_{3}.x-m)^{2}+(d_{3}.y-n)^{2}\leq d_{3}.r_{2}\)**then** \\
54: & **break** \\
55: & **endif** \\
56: & \(D\gets D\cup\{d_{3}\}\) \\
57: & \(d\gets d_{3}\) \\
58: & \(d_{1}\gets D\{2\},d_{2}\gets d.south,d_{3}\gets d.west\) \\
59: & **if**\((\sqrt{(d_{1}.x-d.x)^{2}+(d_{1}.y-d.y)^{2}}\leq d_{1}.r+d.r)\) and \((d_{2}.x+d_{2}.r\geq m\) or \(d_{3}.y+d_{3}.r\geq n)\)**then** \\
60: & **if**\(d_{2}.x+d_{2}.r\geq m\)**then** \\
61: & \(x_{3}\gets x_{4}\gets m\) \\
62: & \(y_{3}\gets d_{2}.y+\sqrt{d_{2}.r^{2}-(m-d_{2}.x)^{2}}\) \\
63: & \(y_{4}\gets d_{1}.y+\sqrt{d_{1}.r^{2}-(m-d_{1}.x)^{2}}\) \\
64: & \((x,y,r,h,b,e,h_{ref})\leftarrow(d.x,d.y,d.r,d.h,d.b,d.e,d.h_{ref})\) \\
65: & \(\mathit{indication}\leftarrow\mathit{EquDistant}(d,\{(x_{3},y_{3}),(x_{4},y_{4})\},1)\) \\
66: & **if**\(\mathit{indication}=0\)**then** \\
67: & **if**\(((x_{1}-d.x)^{2}+(y_{1}-d.y)^{2}>d.r_{2})\) or \((x_{2},y_{2})\) are \(\mathit{defined}\) and \((x_{2}-d.x)^{2}+(y_{2}-d.y)^{2}>d.r_{2})\)**then** \\
68: & \((d.x,d.y,d.r,d.h,d.b,d.e,d.h_{ref})\leftarrow(x,y,r,h,b,e,h_{ref})\) \\
69: & **endif** \\
70: & **else** \\
71: & **break** \\
72: & **endif** \\
73: & **else** \(\mathit{if}_{3}.y+d_{3}.r\geq n\)**then** \\
74: & \(x_{3}\gets d_{3}.x+\sqrt{d_{3}.r^{2}-(n-d_{3}.y)^{2}}\) \\
75: & \(x_{4}\gets d_{1}.x+\sqrt{d_{1}.r^{2}-(n-d_{1}.y)^{2}}\) \\ \hline \end{tabular}   
In the best case,  
\[r =H_{max}\times tan\alpha\] \[\Rightarrow T(n) =O(\frac{m\times n}{\pi(H_{max}\times tan\alpha)^{2}-\mathcal{W}})\]  
In the worst case,  
\[r =H_{min}\times tan\alpha\] \[\Rightarrow T(n) =O(\frac{m\times n}{\pi(H_{min}\times tan\alpha)^{2}-\mathcal{W}})\]  
In the average case,  
\[r =(\frac{H_{max}+H_{min}}{2})\times tan\alpha\] \[\Rightarrow T(n) =O(\frac{m\times n}{\pi((\frac{H_{max}+H_{min}}{2})\times tan \alpha)^{2}-\mathcal{W}})\]  
where  
* \(\alpha\) is the coverage angle
* H\({}_{max}\) is the maximum possible altitude
* H\({}_{min}\) is the minimum possible altitude