There are three movies in this directory, named original.mov,
random.mov and computer.mov. The suffix means that the movies are in
QuickTime format.

They were made by David Epstein and Will Casey, working
collaboratively. We first downloaded from the Internet some public
domain mocap (Motion Capture) files. The hardest part was decyphering
the BVH format often used in the mocap industry. We were unable to find
a formal description of BVH: there was a vague description, with
crucial details missing. This industry seems to define the format
through the C-code that manipulates it, rather than by a mathematical
description.

Using perl, Matlab and Mathematica, we obtained from the public domain
BVH files data that enabled us to animate a stick figure (see
original.mov). The individual frames were put together into a movie
using Quicktime Pro.

Two figures are shown in each frame. The left-hand figure represents
the view from a fixed camera. The right-hand figure represents the view
from a camera travelling with the figure, at a constant distance.

We then randomized the frames, getting the movie random.mov.

Finally, we applied our snapshots-to-movies algorithm to the randomized
frames and obtained the movie computer.mov.

Our algorithm uses a minimum spanning tree (MST).  More precisely, the
stick figure in the movie is specified by the 3d coordinates of around
30 joints. So we are working in a 90-dimensional space, where the Curse
of Dimension comes strongly into play. To compute the MST, one needs to
know, given one of the points, what the nearest point is. Naively, this
takes time O(N^2 d) where N is the number of points and d is the
dimension, and it would have taken a long time with our data.  Using
clever algorithms (all of them standard) we cut down to an
O(N.log(N).d) algorithm---this took about 10 minutes on a standard
desktop.

Once the MST is constructed, there is a linear algorithm to find the
two points in the MST that are furthest apart, where distance is
measured along the tree. The movie computer.mov was constructed by
using the frames that were indicated by following this path. THERE WAS
NO HUMAN INTERVENTION.

There is a 50% chance of reconstructing the path in the wrong
direction, and, by chance, this happened in the construction of
computer.mov from random.mov.