Spring 2003, Computational Geometry Projects
Value of the project:
All projects turned in before the final will get a perfect score.
What will vary is how much the project as a whole is worth.
A solid project on one of the below topics is expected to be worth
about 15% of your total grade. Projects with a significant "wow"
factor may count for as much as 35% of the total grade.
Projects turned in after the final will have a max value of 15% of the
total grade, and are not gaurunteed to get a perfect score. (i.e.,
they may hurt your grade). These project ideas are broken up into different categories:
Category One: Pedagogy (Graphical Applets)
The applets are meant to
illustrate concepts learned in class --- it is not sufficient to just
implement the algorithm, your implementation must also highlight
(visually) the important points of what the algorithm is doing.
COLLABORATION POLICY: There is a great deal of JAVA code and otherwise
that is publicly available on the web. You are welcome to use this,
BUT you must reference where it came from, and clearly indicate WHAT
functionality you have added to the original code. There are no team
projects, but you are welcome to share code with each other to do
input/output of points and line segments.
example project:
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/art_gallery/artgal.html
1) An applet showing the running of the "merge-sort" type of convex
hull construction algorithm. (The applet should show every edge that
is tested as the algorithm runs, including, for example, which edges
are tested when finding the common lower tangent of two sub hulls).
2) An applet showing Kirkpatrick's triangular decomposition data
structure for point location (from lecture 13). (The applet should
have a side by side picture. On the right, the "decomposition tree",
whose root node represent the whole enclosing triangle, and on the
left, the original set of points, and the set of triangles which the
query point is being tested against).
3) An applet showing the line-segment intersection plane sweep
algorithm. Should show the sweep line itself, the known events, and
the segments that are on the sweep line, and highlight the changes
that happen during events.
4) An applet showing the plane sweep algorithm to construct a
trapezoidal map. Should show the sweep line itself, the known events,
and the segments that are on the sweep line, and highlight the changes
that happen during events.
Category Two: Work on Open Problems
This can take the form of a paper (a) describing the current best
algorithms for these problems, the best bounds on the running time of
these algorithms, and (b) a description of your approaches to these
problems. YOU DO NOT have to improve on the best known bounds for
these algorithms, but you do have to carefully document what
approaches you tried, why they worked/failed. The expected result of
this would be a roughly ten page paper (with diagrams and references).
1) Find the complexity of the
Minimum Weight
Triangulation problem.
2) Euclidean Minimum Spanning Tree: Give an algorithm to compute the
minimum spanning tree of a set of points in time O(n log n).
Category Three: Esoterica
One of the claims I've made is that Computational Geometry is useful
for many different fields. Here is your chance to help me prove
that statement:
1) In an artistic forum Voronoi Art
2) Questions relevant to your work:
(a) Implement a dynamic voronoi
diagram for a collection of moving points (mobile computers?).
(b) Problems of your choosing