2019–20 Projects:

Recently, there have been many news stories about space debris. There are, according to Wikipedia, over 300,000 pieces of space junk below 2000 km altitude. As of 2009, NASA and the US Department of Defense were actively tracking approximately 19,000 pieces larger than 5cm, making collision avoidance maneuvers of various satellites when necessary.

Suppose you wanted to track 19,000 objects (or 300,000) in real time, with graphical display of objects moving in three dimensions, and little red flashes when two objects start to get too close to one another. You could move your model forward one time step, compare every pair of objects for distance, and highlight the display where there's danger. Let's see, that's 19000 * 18999 / 2, at let's say 30 frames per second...yikes! Even with N in the hundreds or low thousands, exhaustive pairwise comparison won't be able to yield a real-time display on most devices. And 300,000? Forget about it. Maybe we need a better way to approach this problem.

This problem--detection and analysis of close neighbors in a collection of objects--has lots of applications. Air traffic control systems. Keeping track of non-player characters in a massively multi-player on-line game. Atoms in a billiard-ball-style simulation of gas dynamics. Etc.

As it happens, there's a beautiful sub-field of Algorithms known as Computational Geometry, and it is full of cool data structures and algorithms for solving the kinds of problems you need to solve here. A good solution to the "k nearest neighbors" problem, for example, would allow us to look at each of our 19,000 pieces of debris and just k of its closest pals, instead of all N^2/2 of the pairs of debris. Enter the Voronoi Diagram and the Delaunay Triangulation: these sophisticated data structures can lead to very fast algorithms for dealing with large-N systems, and thus to real-time displays that you might not expect were possible.

In this project, you will develop a system for displaying large numbers of objects in motion, with real-time detection (and mitigation, if appropriate) of close encounters between objects. Some of the tasks before you will include:

- Research the data structures and algorithms required to dynamically track interactions between objects in motion.
- Implement a simple animation and tracking system for objects in two dimensions, using simple data (e.g. randomly generated positions and velocities) and simple interaction behavior (e.g. change direction when you get too close to another object). This stage of the project will help you get to know the data structures, algorithms, and problem domain.
- Choose one or two concrete application areas. (Space debris, for example, would move the problem to 3D, would require you to model orbital physics, and would enable you to use real data about real debris.)
- Develop suitable tracking systems and user interfaces for your chosen application areas.
- Compare the performance of your systems against a brute force N^2 approach.

This is a tricky set of problems, and you may find yourself nudging computational geometry forward in small ways. (For example, what techniques will you use to efficiently update a static data structure when your data points keep moving every thirtieth of a second?) Even if you only use existing techniques, this is a great opportunity to get to know a beautiful area of algorithms theory and practice.

Note that this project will involve reading computational geometry literature, understanding the statements and sometimes the proofs of relevant theorems, and implementing some tricky data structures. In brief, this project has a significant mathematical component, which should make it fun.