Continuous alternation: the complexity of pursuit in continuous domains (Q686740)

The authors propose a generalization of the notion of alternations to differential games and discuss equally polyhedral pursuit games. In a 3-D pursuit game, where each player's velocity is bounded, the pursuit game (corresponding to collision avoidance in robotics), is an exponentially ``hard'' problem in complexity. The authors present a derivation of approximate polynomial time upper bounds. If the obstacles are described with \(n\) bits, and there is a minimum distance \(\varepsilon\) from the pursuer to all obstacles, the evading algorithm runs in time \((n/\varepsilon)^{0(1)}\).