| We study partitioning problems of polygonal domains under requirements of balancing various objective functions. Some of them are specific to Air Traffic Management, but others are more general and have a broader range of applications.;In Chapter 2 we start with a Districting problem, where we are given a partition of a polygon into weighted polygonal subdistricts, and are asked to merge them into a given number of districts while balancing their weights. We consider the problem in 1D and 2D, and the static and dynamic versions of the problem. We show that in 1 D this problem is polynomially solvable, and becomes NP-complete in 2D. We give approximation algorithms for several special cases of the problem.;In Chapter 3 we study the Airspace Sectorization problem, where the goal is to find a sectorization, i.e., a partition of the airspace into sectors, under a number of requirements on the geometry of the sectors, as well as on the air traffic flow-conformance, while balancing the controllers' workload. In Chapter 4 we propose a Local Redesigning Method (LRM), a heuristic that rebalances a given disbalanced sectorization by applying small local adjustments to the sectors boundaries. We evaluate LRM experimentally on synthetically generated scenarios as well as on the real historical traffic data and demonstrate that the sectorizations produced by our method are superior in comparison with the current sectorizations of the US airspace.;In Chapter 5 we propose a point-balancing convex polygonal partitioning problem defined in the following way: Given a polygon and a set of points in it, partition the polygon into the minimum number of convex pieces having a limited number of points in each piece. We present two optimal algorithms for the case of a simple polygon with some restrictions on the partitioning cuts. We also give a number of approximation algorithms for different variations of the problem. |
