Congratulations and thank you for your contribution to Clinical Psychology. Now that the book is published, we need your help to get some 5 star reviews posted to both Amazon and Barnes & Noble to help support and promote it. As you know, these online reviews are extremely persuasive when customers are considering a purchase. For your time, we would like to compensate you with a copy of the book under review as well as a $25 Amazon gift card. If you have colleagues or students who would be willing to post positive reviews, please feel free to forward this e-mail to them to participate. We share the common goal of wanting Clinical Psychology to sell and succeed. The tactics defined above have proven to dramatically increase exposure and boost sales. I hope we can work together to make a strong and profitable impact through our online bookselling channels.Naturally, it was all a mistake.
« May 2009 | Main | July 2009 »
June 23, 2009
June 21, 2009
June 16, 2009
June 15, 2009
How hard is optimal racing?
David and Suresh (two three) have done a good job summarizing the research highlights at SOCG. But nobody has mentioned the real highlight of the conference: The post-conference go-kart race!
Math geek that I am, the noise and speed and adrenaline reminded me of one of my favorite open problems, which is based on a pencil-and-paper game I played on the schoolbus in 5th grade, called Racetrack (or Graph Racers, or Vector Racer, or Vector Rally, or...). (They were really fast school buses.) The origins of the game are unclear. Martin Gardner described it in a 1973 "Mathematical Games" column (reprinted as Chapter 9 of Knotted Doughnuts and Other Mathematical Entertainments).
The game is played with a track drawn freehand on a sheet of graph paper, with a starting region and a finish region. The players alternately choose a sequence of grid points that represent the motion of a car around the track, subject to certain constraints explained below. The car that reaches the finish region first wins the race.
Each car has a position and a velocity, both with integer x- and y-coordinates. Each player chooses an initial position in the starting region; the cars all start with velocty (0,0). At each turn, the player optionally increments or decrements either or both coordinates of the car's velocity; in other words, each component of the velocity can change by at most 1 in a single step. The car's new position is then determined by adding its new velocity to its previous position. The car's new position must lie inside the track; otherwise, the car crashes and that player loses the race.
(The actual game I played had more complicated rules about running off the edge of the track, but here let's keep things simple. In particular, let's not require the entire line segment between any two successive positions to lie inside the track. Cars can jump over the walls, as long as each jump lands inside the track.)
The Racetrack game suggests a natural algorithmic problem: Compute the optimal racing strategy for a given racetrack. The difficulty of this question depends on how the input racetrack is represented. In other words, it depends on the definition of the word "given"!
The most obvious (and realistic) input reprsentation is an array, where each entry A[i,j] indicates whether the point (i,j) is off the track, in the starting region, in the finish region, or in the middle of the track.
With this input representation, the optimal racing strategy is easy to compute in polynomial time. Build a directed graph whose nodes resprsent all legal posision-velocity pairs, and whose edges represent legal moves. Add a source vertex s, and an arc s->((i,j),(0,0)) for every point (i,j) in the starting region. Add a target vertex t, and an arc ((i,j),(u,v))->t for every point (i,j) in the finish region and every legal velocity (u,v). Finally, perform a breadth-first search from s to find the shortest path to t. If the input array has n rows and n columns, this algorithm runs in O(n^3) time. (Why n^3 instead of n^4? I'll leave that as an exercise.)
But a more natural input representation, at least for computational geometers, is a set of line segments that delimit the boundary of the racetrack (and the boundaries of the start and finish regions). To keep the problem solvable, let's assume the endpoints of these line segments have integer coordinates.
Of course we could still build the configuration graph, but this could require exponential space! Even if the track is just an N×N square, the input requires only n = O(log N) bits, but the configuration graph has complexity Θ(N^3) = 2^{Ω(n)}. Moreover, even if we don't build the entire graph, any explicit description of the optimal path—or any legal path—could have exponential complexity. So if we want any hope of an efficient algorithm, we have to change the problem.
One reasonable variant would be to find the minimum number of turns. It's not hard to show that this verison of the problem is in PSPACE—it's morally equivalent to reachability in a graph of exponential complexity—but I don't know how to do any better than that. In fact, that's the best upper bound I know even for the simpler reachability question: Is there any sequence of legal moves that takes a car from the start region to the finish region? Even if we didn't allow cars to jump over walls, narrow corridors with sharp corners would make this decision problem nontrivial. Can the racetrack reachability problem be solved in polynomial time? Is it even in NP? Or is it PSPACE-complete?
Alternately, we could require some kind of compressed output representation. For example, we could represent paths in the following form: accelerate northwest for 42 turns, then west for 17 turns, then southeast for 23 turns,.... Unfortunately, the optimal path might still have exponential complexity in this representation. Consider a corridor defined by two close parallel line segments with slope close to the golden ratio. The sequence of grid points between those segments is aperiodic; in the limit, it approaches the infinite Fibonacci word.
But maybe we can get a polynomial-length representation using something more subtle, like Lempel-Ziv compression, and then maybe we can actually compute the compressed representation in polynomial time. (For a similar approach, see Schaefer and Sedgwick's algorithm for computing Dehn twists and intersection numbers.) Is there a polynomial-time algorithm that outputs any reasonable compressed representation of the optimal path? ("The optimal path for the following track
Of course a real computational geometer (ahem) might try to get rid of the grid entirely. In a more continuous variant, both the positions and velocities of the cars would be real vectors, and in each turn, a player could change their velocity by adding any vector of (Euclidean) length at most 1. This variant obviously avoids problems due to integer aliasing, but is there any hope of solving it efficiently? Is it even still in PSPACE?
Recent Comments