## 2 Background and Related Work
In such cases, the CPP problem is divided into several small start-to-goal subproblems, where UAV needs to visit each POI only once while avoiding collision with the obstacles present in the AOLSome authors considered the special cases of CPP in which AOI contains many interesting and non-interesting zones [43; 44]. The interesting zones need careful coverage with higher resolution, so UAV covers such zones with low altitudes and vice versa.A new CPP approach for the aerial remote sensing in agriculture was proposed by [PERSON] et al. [45]. The proposed approach decomposes the AOI based on the vehicle's capabilities. UAV has to fly at a certain constant height in order to ensure a specific resolution and CPP is performed using a wavefront planner [46]. The existing studies used several path optimization algorithms for UAV CPP. The ant colony optimization (ACO) [47], Genetic algorithm (GA) [48], wavefront algorithm [49], A\({}^{*}\) algorithm [50], theta\({}^{*}\) algorithm [51], particle swarm optimization (PSO) [52], and their improved versions, among other, are the most widely used path optimization algorithms for CPP. A number of studies have explored a closely related method used for UAV CPP with coverage guarantees, the boustrophedon cellular decomposition based hierarchal CPP approach  
Figure 1: Most widely used areas of interest decomposition techniques for coverage path planning. (BCDH-CPP) [53], and the related coverage alternatives-based CPP (CA-CPP) algorithm [54]. The BCDH-CPP [53] is a cellular decomposition based CPP approach for the UAVs and it is a promising method for CPP in known environments inhabiting arbitrary obstacles. The proposed approach decomposes the AOI into cells, compute a Eulerian circuit traversing through these cells, and finally joins each cell in using seed spreader motion pattern to find a coverage path. The proposed approach determines the coverage path with excessive overlapping in some parts by not considering the UAV sensor/camera footprints as coverage unit. CA-CPP algorithm [54] introduced the four coverage alternatives to perform efficient coverage in both convex and non-convex areas. The proposed approach can reduce the number of turns and path length considering the appropriate directions and optimal line sweep. The proposed approach has very high computational cost. Meanwhile, the authors devised a method to reduce the overheads by enforcing adjacencies. However, due to extensive evaluation of various permutations, the proposed algorithm complexity varies exponentially with problem size. Furthermore, the decomposition-based CPP approaches discard the useful global information about the free spaces geometry which can lead to the excessive number of turns in the path. The contributions of this research in the field of UAV global CPP can be summarized as follows: (i) it proposes a new coverage flight path planning algorithm that has potentials to obtain the minimum length path that ensures the perfect coverage of the target area with reduced computational time, number of turns, and path overlapping; (ii) it evaluates and selects the best coverage direction(s) by analyzing the span of the AOI, and exploiting free spaces geometry information to reduce the number of turns in the path; (iii) it introduces a novel footprints' sweeps fitting method in which an entire free space of a certain AOI can be swept with fewer and longer sensor/camera footprints' sweeps; (iv) it determines the visiting sequence of the footprints' sweeps in the form of closed path to reduce the global path length; (v) it generates a sparse waypoint graph by connecting the footprint sweeps' endpoints with neighbours' sweeps by taking into account their visiting sequence, UAV maneuverability constraints, and obstacles effect; (vi) it finds a coverage path that fully scan the desired area located in 3D urban environments.