This work focuses on the problem that pertains to area searching with UAVs. Specifically developing algorithms that generate flight paths that are short with- out sacrificing flyability. For instance, very sharp turns will compromise flyability since fixed wing aircraft cannot make very sharp turns. This thesis provides an analysis of different types of search methods, area decompositions, and combi- nations thereof. The search methods used are side to side searching and spiral searching. In side to side searching the aircraft goes back and forth only making 90-degree turns. Spiral search searches the shape in a spiral pattern starting on the outer perimeter working its way in. The idea being that it should generate flight paths that are easy to fly since all turns should be with a large turn radii. Area decomposition is done to divide complex shapes into smaller more manage- able shapes. The report concludes that with the implemented methods the side to side scanning method without area decomposition yields good and above all very reliable results. The reliability stems from the fact that all turns are 90 degrees and that algorithm never get stuck or makes bad mistakes. Only having 90 degree turns results in only four different types of turns. This allows the airplanes behav- ior along the route to be predictable after flying the first four turns. Although this assumes that the strength of the wind is a greater influence than the turbulences effect on the aircraft’s flight characteristics. This is a very valuable feature for an operator in charge of a flight. The other tested methods and area decompositions often yield a shorter flight path, however, despite extensive adjustments to the algorithms they never came to handle all cases in a satisfactory manner. These methods may also generate any kind of turn at any time, including turns of nearly 180 degrees. These turns can lead to an airplane missing the intended flight path and thus missing to scan the intended area properly. Area decomposition proves to be really effective only when the area has many protrusions that stick out in different directions, think of a starfish shape. In these cases the side to side algo- rithm generate a path that has long legs over parts that are not in the search area. When the area is decomposed the algorithm starts with, for example, one arm of the starfish at a time and then search the rest of the arms and body in turn.

Baigiamajame magistro darbe nagrinėjama paprasto skylėto daugiakampio skaidymo į dalis, kurių viršūnių skaičius neviršyja nustatyto skaičiaus problema. Apibrėžiamas uždavinys ir jo svarba. Apžvelgiami egzistuojantys skaidymo algoritmai, padedantys išspręsti uždavinį, bei jų realizacijos. Pateikiamos trianguliacijos ir padalinimo į apytiksliai iškilius daugiakampius algoritmų modifikacijos, jų privalumai ir trūkumai. Įvertinamas šių modifikuotų algoritmų sudėtingumas. Eksperimentinėje dalyje pateikiami skaičiavimo eksperimentų rezultatai, jų analizė ir palyginimas su teoriniais algoritmų sudėtingumo įverčiais. Remiantis skaičiavimo eksperimentų rezultatais pateikiamos išvados ir siūlymai. / This study deals with decomposition of simple polygon with holes into components so that every piece does not exceed some defined number of vertices. We define the problem and its appliances. Existing studies and algorithms for polygon decomposition are covered. We propose modifications of polygon triangulation and approximate convex decomposition algorithms. Also the complexity analysis of both algorithms is made. In the experimental part of the work results of computing experiments are presented, analyzed and compared to the theoretical complexity bounds.