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?