###### Abstract
In the latter scenario, the number of deployed UAVs is more than one, unlike the former in which only one UAV is deployed. The process for finding a path generally begins with searching a waypoint/visibility graph from one location and progressing until the target is found. The quality of a PP method usually relies on choosing low-cost path waypoints from a given graph that contributes to an optimal/quasi-optimal path with the fewest computations. This study focuses on a single-UAV PP problem, and our aim is to lower the time complexity without degrading the path quality. Many global PP solutions have been designed for augmenting a UAV's autonomy in various practical missions in the airspace [24; 25; 26; 27; 28]. The pathfinding procedure mainly encompasses three key steps: (i) modeling the operating environment (e.g., the environment's representation with a graph), (ii) employing a search algorithm on the graph to determine a path, and (iii) applying a heuristic function (e.g., smoothness, energy, distance, or turns) that accompanies the path search. UAV operating-environment depiction with precise geometry is imperative in order to determine a low-cost path. Roadmap [29], cell decomposition [30], and potential field [31] are renowned environment representation approaches for the configuration space. The search algorithm analyzes the graph for low-cost pathfinding. Many algorithms for PP on graphs have been developed since 1959 such as [PERSON]'s algorithm [32] and best first search-based greedy algorithm [33]. Both of these algorithms are regarded as pioneer pathfinding algorithms based on a graph search. However, the A* algorithm [34] is known as the benchmark and is extensively used for a low-cost path search. It is more robust than [PERSON]'s algorithm and its variants. Aside from these famous algorithms, many improved versions of the A* algorithm such as IDA* [35], Theta* [36], Lazy-theta* [37], LPA* [38], and D*-Lite [39] also have the ability to find a working path. Most of the prior PP methods for UAVs do not present deep insights into space reduction with a good-quality path guarantee, specifically regarding the effective resolution of the speed-versus-optimality trade-off in complex 3D urban environments. The prior PP solutions mainly focus on constructing better heuristic functions, and, thereby, memory overhead can occur. Most algorithms sacrifice either optimality or speed while finding paths. Meanwhile, in many practical applications for a UAV, the trade-off on any of the given metrics (e.g., speed or optimality) is not tolerable. Hence, it is mandatory to reduce exploration and modeling of low-probability spaces to overcome these computing issues. Various space modification methods have been designed to increase the pathfinding speed, such as abstractions in a hierarchical form [40], symmetry breaking [41], sub-goal graphs [42], jump-point searches [43], accurate heuristics [44], compressed path databases [45], pruning dominant states [46], swamp hierarchies [47], influence-aware pathfinding [48], and constraint-aware methods for navigation [49]. Besides the validity of these latest developments, in most cases, either many low-priority locations of a map are searched uselessly or path quality significantly degrades. Recently, a number of studies considered reducing computation times by dealing with pertinent obstacles that are only crossed along a straight axis in the pathfinding process [50; 51]. However, these mechanisms have higher computational complexity and yield non-taut paths if obstacle density is high. Hence, these methods are vulnerable to either returning longer paths or demanding more computing power in determining a path. To address the above limitations, this study presents a new PP method that significantly lowers pathfinding computing time without impacting path lengths by leveraging a Constrained Polygonal Space (CPS) and an Extremely Sparse Waypoint Graph (ESWG) while finding a working path from a 3D urban environment.