Maximum thick paths in static and dynamic environments

We consider the problem of finding a maximum number of disjoint paths for unit disks moving amidst static or dynamic obstacles. For the static case we give efficient exact algorithms, based on adapting the "continuous uppermost path" paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem. (In this extended abstract we only state these results.) Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. We observe that (unless P=NP), for any α, β > 0, one cannot decide in polynomial time whether there exist [αK] paths for disks of radius βR, where K is the maximim number of paths for radius-R disks. The problem is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying "dual" approximations, compromising on the radius of the disks and on the maximum speed of motion. Our main result is a pseudopolynomial-time dual-approximation algorithm: if K unit disks, each with unit bound on the speed, may be routed through an environment, our algorithm finds (at least) K paths for disks of radius Ω(1) moving with speed O(l). The algorithm computes a maxflow with "forbidden pairs" in an "adaptive" grid, laid out in space-time. Although (as we show) in general finding even an approximation to the maxflow with forbidden pairs is not possible (unless P=NP), a careful choice of time discetiza-tion and a non-uniform grid of "way-points" allows us to give provable approximation guarantees on the quality of the solution produced by the algorithm, paths for translational motion of arbitrary-shape objects.