Sponsors: ONR, NSF
Guibas recently developed a family of data structures for constructing convex hulls, Voronoi diagrams, and finding the closest pair in a set of moving points. Briefly, if the motion of the points is known, then the data structures can be used to predict when a change must happen in these geometric computations and how they should be updated. The update itself is accomplished by running a tournament.
Suppose we have two types of moving points, blue and red, and we are interested in all red/blue pairs that approach each other closer than a particular distance. Then basic changes must be made to the algorithms in order to report all such pairs. As an application, consider team sport where the blue team will tackle any red team member who is ``within reach.'' Assuming that the coach of the blue team manages the contest, all red team members within reach should be reported so that decisions can be made on how to respond to the situation.
For an example of this kind, please see http://www.cs.purdue.edu/homes/kimy/KDS/kds.html where a snap shot of this situation is shown in the first picture. Here, the green lines identify all red/blue pairs that are within threshold distance.
At that site you can also find some variations of the problem. For example, another picture illustrates the case when the reach of a player is not equal in all directions. These and other model scenarios are under investigation in this research.