Closest Pair Applications: Ray-Intersection Diagram
(or, Crashing Motorcycles Efficiently)

Click and drag to specify the initial locations and velocities of a system of moving particles. Each particle stops moving when it crosses the track left by another particle.

If you were viewing this on a Java-enabled browser, you'd get to play with my extremely exciting applet. Since you're not, you might as well just follow the following links, since I have no other content here:

For more detailed information on this diagram, see Jeff Erickson's page "crashing motorcycles efficiently". This implementation is based on the FastPair version of our closest pair data structures (with nearest neighbors found by sequential search rather than geometric range searching); see the source code for details.

David Eppstein, Dept. Information & Computer Science, UC Irvine, .