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?
Nicely done - you give a very good summary of the problem. I first tangled with the optimal racing problem while working through Brian Beckman's Physics of Racing series, and it continues to fascinate me.
Posted by: EastwoodDC | June 17, 2009 at 07:35 AM