Maximum thick paths in static and dynamic environments (Q5902231)

The authors consider the problem of finding a large number of disjoint paths for unit disks moving static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding ``no-fly zones'' and predicted weather hazards. For the static case, an efficient exact algorithms is given based on adapting the ``continuous uppermost path'' paradigm. As a by-product, a continuous analogue of Menger's theorem is established. The main result of the paper is a pseudopolynomial-time dual-approximation algorithm. If \(K\) unit disks, each moving with speed at most 1, can be routed through an environment, the proposed algorithm finds (at least) \(K\) paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1. For that purpose, a discretization of time and space is employed using hexagonal grids. The conflicts between the computed paths introduced by the discretization can be resolved locally.