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.)
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:
- 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
endfor
This case is handled in linear time, but it happens only once.
The overall time to construct the motorcycle graph in this case is O(n log n),
which is optimal.
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?
Open Problems -
Jeff Erickson
(jeffe@cs.duke.edu)
08 Feb 1998