  One-clock priced timed games is a class of two-player, zero-sum,
continuous-time games that was defined and thoroughly studied in previous
works. We show that one-clock priced timed games can be solved in time m 12^n
n^(O(1)), where n is the number of states and m is the number of actions. The
best previously known time bound for solving one-clock priced timed games was
2^(O(n^2+m)), due to Rutkowski. For our improvement, we introduce and study a
new algorithm for solving one-clock priced timed games, based on the sweep-line
technique from computational geometry and the strategy iteration paradigm from
the algorithmic theory of Markov decision processes. As a corollary, we also
improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and
Larsen; and Alur, Bernadsky, and Madhusudan.
