## 2 Background and Related Work  
This section presents the background and related work regarding the AOI decomposition techniques used for UAV CPP, coverage types, different types of the AOI used for coverage missions, geometric flight patterns, path optimization algorithms and application specific CPP methods. [PERSON] et al. [29] defined the six requirements for coverage scenarios. In complex environments, it is not always possible to satisfy all six requirements. Therefore, in some cases, the priority is given to the mission completion with sacrifice on some of the requirements [30]. Prior research classified the CPP methods into two major categories: heuristic and cell decomposition-based methods. Heuristic based methods define procedures that should be followed during CPP [31; 32]. In cell decomposition, the AOI is decomposed into non-overlapping cells of varying shapes and sizes. There exist several kinds of the AOI decomposition techniques in literature [30]. Boustrophedon decomposition [33] and trapezoidal decomposition [34] are two well-known exact cellular decomposition techniques that are widely used for coverage applications. Morse-based cellular decomposition is an advance form of the boustrophedon decomposition which is based on critical points of Morse functions [35]. The approximate cellular decomposition techniques divide the AOI into a set of regular cells. Grid-based methods are used over approximate areas to generate coverage paths for the UAVs [36]. Convex decomposition transforms the irregular shaped AOI into regular shaped cells in order to reduce the number of turns [37]. Each decomposition method varies regarding the cell sizes, cell shapes, degree of computational complexity, and path quality. A pictorial overview of the most widely used AOI decomposition techniques is given in Figure 1.  
There are two types of coverage: simple and continuous. The shape of the AOI can be a rectangle, square, convex polygon, non-convex polygon, 3D cubes (i.e., buildings) or irregular for coverage missions. The most widely used geometric flight patterns for CPP are back and forth (BF), spiral (SP), zamboni, and hybrid patterns. [PERSON] et al. [38] compared different types of the geometric flight patterns in his work. The flight patterns are employed considering the UAV mobility constraints, shape of the AOI, coverage type, and application requirements. For example, the BF pattern is suitable when the AOI is rectangular and large in size. [PERSON] et al. [39] proposed an exact cellular decomposition based approach for concave area coverage. Initially, the concave shaped AOI is decomposed into the convex subareas using the minimum width sum approach [40], and then the BF motion pattern is applied to completely sweep the AOI. [PERSON] et al. [41] proposed an optimal CPP approach for fixed wing UAVs with minimum overlapping and coverage guarantees. The proposed algorithm employs the boustrophedon decomposition to decompose the AOI into a set of cells. Later, the adjacency graph is constructed from the cells, and cells are swept using the BF motion patterns. The order of the cells visit follows the Eulerian circuit having start and end at the same vertex. The proposed approach is able to achieve the complete coverage of the AOI. However, in some cases, it will perform additional sweeps by not considering the sensor's footprint that will significantly affect the solution quality in the presence of complex geometry obstacles. [PERSON] [42] proposed a CPP approach for concave shape AOI with sharp edges without sacrificing the guarantees on complete coverage. In some scenarios, a UAV needs to visit several spatially distributed points of interests (POIs) in the target area to either collect data or provide wireless charging during the mission.