  In this paper we study the Airspace Sectorization Problem (ASP) where the
goal is to find an optimal partition (sectorization) of the airspace into a
certain number of sectors, each managed by an air traffic controller. The
objective of the ASP is to find a "well-balanced" sectorization that
distributes the workload evenly among the controllers. We formulate the ASP as
a partitioning problem of a set of moving points in a polygonal domain. In
addition to the requirement of balancing the workload, we introduce
restrictions on the geometry of the sectorization which come from the Air
Traffic Management aspects. We investigate several versions of the problem that
arise from different definitions of the notion of the workload and various
choices of geometric restrictions on the sectorization. We conclude that most
of the formulations of the problem, except maybe in some trivial cases, are
NP-hard. Finally, we propose a Local Redesigning Method (LRM), a heuristic
algorithm that rebalances a given sectorization by adjusting the boundaries of
the sectors. We evaluate LRM experimentally on synthetically generated
scenarios as well as on the real historical traffic data. We demonstrate that
the sectorizations produced by our method are superior in comparison with the
current sectorizations of the US airspace.
