Imagine several people riding motorcycles out in the desert. The bikes are extremely fragile; if any motorcycle runs over the track previously left by another bike, it immediately crashes. If two bikes reach the same point simultaneously, they both crash. Fans of cheesy science fiction movies will recall the movie TRON, in which "Light Cycles" drove around an arena, leaving walls behind them. If a light cycle ran into a wall, it would "derez" and its wall would disappear. In our scenario, even after a cycle derezzes, its wall stays up.)
Two and a half light cycles.
A light cycle derezzing.
Images stolen from Spike's TRON Website.
How quickly can we determine which bikes crash into which tracks and which bikes survive? To make things a little more concrete, let's suppose that all the bikes start moving simultaneously and that once they start, each bike moves in a straight line at a fixed speed; no turning, accelerating, or braking is allowed. After all the bikes either crash or escape unharmed, the tracks will form a graph like this:
This motorcycle graph has at most 2n vertices and 2n edges. The graph can contain cycles (appropriately enough), but each connected component contains either one cycle or one edge going off to infinity. (If you want a proper graph, imagine that the surviving bikes eventually run out of gas.) The problem is to draw this graph efficiently, given the initial locations and velocities of the motorcycles. David Eppstein has written a Java applet that illustrates motorcycle graphs.
There is an easy algorithm to draw the motorcycle graph in O(n2 log n) time and O(n2) space. For each pair of bikes, determine whether their two paths cross, and if so, when the later bike reaches the crossover point. Sort these events chronologically, and scan through them in order. Most of the time we will find that the crossing doesn't really happen, because one or both bikes stopped before reaching the crossover point. In this case we just ignore the event. If both bikes survive to the crossover point, then the later bike stops there.
By maintaining a triangulation or trapezoidal decomposition of the evolving graph, we can reduce the space requirement to O(n), keeping the same running time. Afternatively, we can reduce the running time to O(n2), keeping the same space bound, by using a quadtree-like data structure of David Eppstein. Recently, David and I discovered the first subquadratic algorithm, with a running time of O(n17/11+e) for any fixed e>0; see our paper "Raising roofs, crashing cycles, and playing pool" for details.
Although we have (finally) a subquadratic algorithm, both the simplicity of motorcycle graphs and the bizarre running time suggests that we can do better. Is there a near-linear-time algorithm to construct the motorcycle graph? To determine how many motorcycles escape, or if any escape at all? To determine the fate of even one motorcycle? O(n log n) algorithms are known for a few special cases, which I'll describe below, but a new idea is required to solve the general problem more quickly. Near-linear time may be too much to hope for; perhaps the right time bound is O(n3/2) or O(n4/3).
An easy reduction to sorting implies that we need Omega(n log n) time to construct the motorcycle graph, at least in the algebraic decision/computation tree model. The graph below illustrates one reduction (but not the simplest); details are left as an exercise for the reader. I'm not sure whether the lower bound applies to the other problems. Can this lower bound be improved?
The first special case we can solve quickly is when the motorcycles are in two "gangs", one moving in the positive x direction ("The Screaming Ordinates") and the other in the positive y direction ("Hell's Abscissas"), with both gangs starting far away from the lattice of crossover points. Sort the bikes in each gang (Ordinates from bottom up, Abscissas from left to right). Note that the lowest Ordinate and the leftmost Abscissa are guaranteed to both reach the lowest leftmost crossover point. (I didn't notice this until Lars Arge pointed it out to me!) To construct the motorcycle graph, determine which bike crashes at the lowest-leftmost crossover point, draw its path, remove it, and repeat until all the remaining bikes are going the same direction. The total running time is O(n log n), or O(n) if the bikes are already sorted.
More generally, suppose that all the motorcycles are moving from left to right, but not necessarily parallel to the positive x axis. In this case, we can construct the motorcycle graph in O(n log n) time using a simple sweepline algorithm. Sweep a vertical line upwards from left to right, maintaining in a balanced binary tree a current cross-section of the graph. This cross-section can change combinatorially in only two ways: the sweepline passes a bike's initial location ("birth"), and the sweepline passes the crossing point of two adjacent tracks ("death"). These events can be kept in a priority queue, sorted by their y-coordinates. Initially, the event queue contains only the m births. To handle a birth, insert the new track into the binary tree, delete the "death" event (if any) caused by its two neighbors from the event queue, and insert two new "death" events. To handle a "death" event, determine which bike dies, delete it from the binary tree, delete its other "death" event, and insert a new "death" event between its two neighbors. There are at most 2n events, and each event is handled in O(log n) time.
Extending this algorithm to deal with vertical motorcycles is straightforward. Even though it may take O(n log n) time to handle a single vertical bike, this time can be amortized across the bikes that it kills.
Another special case that we can solve quickly is when all the motorcycles' paths are tangent to a given directed closed convex curve, and all the bikes start far away from any crossover points. Here is an example of such a motorcycle graph, which we used earlier to show that constructing motorcycle graphs is at least has hard as sorting.
The motorcycles can be ordered by the angles of their velocity vectors. In the graph above, every bike crashes into the track left by its successor this circular order, although this will certainly not happen in general. However, at least one bike will survive long enough to cross its successor's path, either in front or behind its successor. (Otherwise, if every bike dies before crossing its successor's path, then there's nothing for the bikes to run into.)
This observation leads to the following algorithm. Sort the bikes. For any two bikes i and j, let T(i,j) and P(i,j) be the time and place at which bike i crosses bike j's path, if bike i survives that long. Determine T(i,i+1) and P(i,i+1) for each bike i, and put these events into a priority queue, sorted chronologically. (All addition is taken mod n.)
Suppose bike i is the earliest to cross the path of its successor, bike i+1. There are two cases to consider:
The overall time to construct the motorcycle graph in this case is O(n log n), which is optimal.
- Bike i reaches P(i,i+1) before bike i+1.
In this case, bike i+1 crashes at P(i,i+1). Moreover, nothing will ever crash into bike i+1's track. Draw the complete path for bike i+1, remove P(i+1,i+2) from the event queue, insert P(i,i+2), and repeat. This case is handled in O(log n) time.
- Bike i reaches P(i,i+1) after bike i+1.
In this case, bike i crashes at P(i,i+1), and bike i+1 survives long enough to cross its successor's path. At this point, we can complete the construction of the motorcycle graph by iterating through the bikes, starting with bike i+1, to see who survives each crossover:curr = i+1 for next = i+2 to i-1 (mod n) if curr reaches P(curr,next) before next next crashes at P(curr,next) else curr crashes at P(curr,next) curr = next endif endforThis case is handled in linear time, but it happens only once.
If the bikes are given in sorted order in the input, we still need O(n log n) time if Case 1 happens Omega(n) times before we hit Case 2, but the lower bound is now only Omega(n). Is there a linear-time algorithm?
The motorcycle problem is similar to (a limiting case of) Franz Aurenhammer's problem of computing the straight skeleton. In fact, the straight skeleton of a simple polygon with very sharp reflex angles, or a non-simple polygon with very sharp triangular holes, closely approximates the structure of a motorcycle graph; see below. The motorcycle graph illustrates what's really hard about computing straight skeleta: how do the edges extending from reflex vertices interact?
There is a sense in which this interaction can be made arbitrarily complicated. Given a planar boolean circuit and a set of inputs, we can construct a set of motorcycles with the following properties:
This reduction implies that constructing motorcycle graphs, or even deciding the fate of a single bike, is P-complete, even in very simple special cases. Thus, an efficient parallel algorithm is incredibly unlikely. Similar reductions have been used by Atallah, Callahan, and Goodrich to prove the P-completeness of other geometric problems ["P-complete geometric problems", Int. J. Comput. Geom. Appl. 3:443-462, 1993] and by Griffeath and Moore to prove the P-completeness of certain cellular automata.
- If the output of the circuit is 1, one particular motorcycle survives.
- If the output of the circuit is 0, every motorcycle dies.
- The motorcycles' speeds depend only on the input values.
- The motorcycles' positions and directions depend only on the circuit.
- The motorcycles all travel north, east, or northeast.