## Project Ideas

I would prefer to have small teams working on projects. It is hard to do anything meaningful in a short period of time by yourself; brainstorming with other people is useful for introducing new ways of thinking; and there is more of a chance that at least some members of the group might continue on with the project after the class.

Here are some ideas that seem like interesting applications of computational geometry. If you have a specific research problem that you would like to pursue, come talk to me and we will see if we can find an angle that fits with the theme of this course. Any project should require you to learn or apply some material in computational geometry or spatial data structures; I would prefer something that makes you think about the theory rather than just hack or try out ideas.

• Weighted Centroidal Voronoi Diagrams: This paper in SIGGRAPH 2009 used a specialized kind of Voronoi diagram to distribute points very evenly for digital halftoning and other applications. It is computed, very slowly, by a brute force method. What mathematical properties can you use to produce a better algorithm (not just a better implementation)? The algorithm by Little for reconstrcting a polyhdron from its Extended Gaussian Image might be useful here? Here is a paper on a combinatorial version of the problem, which might be more efficient? (For "just throw it on the GPU", see this).
• Mathematical Visualization: There was a lot of buzz in the combinatorial mathematics world recently about this counterexample to the Hirsch Conjecture. It revolves around the construction of a reasonably small five-dimensional polytope. There are lot of people who would be interested in a video or interactive app to help them "see" this polytope; for inspiration, here is an example of one of my old videos.
• Lines in space: The geometry of lines in three-dimensional space is related to visibility and ray-tracing problems in graphics. This paper in SIGGRAPH 2010 developed a data structure that returns a subset of the input lines that may pass close to a query line. Is there someway to make a data structure that returns only lines that really do pass close to the query line? One idea I've always thought that someone should pursue is a BSP tree in the space of lines.
• Jump-flood: This paper from I3D 2006 gives a very fast, but slightly incorrect, GPU algorithm for 2D Voronoi diagram. Is there some way to do something similar, yet correct? Can the idea be applied in 3D, now that we have bigger texture memories?
• GPU data structures: We are just starting to implement a lot of geometric computations on the GPU. We have seen the implementation of a quadtree as a sorted list, which is appealing since radix sorts on the GPU are now very fast. What additional features do you need to add to this quadtree in order to make it do anything useful? How could these be implemented on the GPU?