CS507A: Computational Geometry - Projects - Advice
The Web project involves publishing a tutorial introduction to a topic
in computational geometry and is
divided into two parts: the HTML document
(counts for 12%) and the interactive Java applet
(counts for 20%). Both the HTML document and the Java applet
are due December 3rd and the entire finished project
must be installed in the Computational Geometry Laboratory
by that date.
For a better idea of what is expected,, take a look at Godfried
Toussaint's previous years
Here are a few things that every project should contain. You are free
to organize the contents as you wish as long as the content is there,
clearly presented and well structured. So don't take the following
items as mandatory sections of your web tutorial, it is only a hint of
the information I would like to find there.
In addition, there are two things I will absolutely need from you:
- Introduction: You tutorial should contain (and maybe start)
with a good overview of the problem. This doesn't need to be
formal. It should give a good motivation to the problem and invite the
reader to read further.
- History and Background: Somewhere in your project, you
should give a history of your topic. Where did the problem come from?
What was the original motivation? When and where did it appear first?
Any funny or interesting anecdotes related to the problem? Has it been
used for something? If your problem is very fundamental and old, don't
hesitate to take a look at some books on the history of math or
history of sciences.
- Related topics: If you are aware of some problems or topics
close to yours, you should say a word about it.
- Formal definition of the problem/topic: Beyond the informal and
inviting presentation you will give at the beginning, there must be
some point where you will be very precise. Define every non-obvious
term you use and so on.
- More on the web and elsewhere: There is a lot of stuff on
the web which are relevant to your topic. Try to include many
links, with useful descriptions.
- References: You should have a reference section. You should
place there a reference to any material you use or refer to. List
papers and books as precisely as possible, include links if they are
accessible online. Make internal links to this list from other places
in your website as needed.
- A title: The name of a paper/project/website is extremely
important. This is how it will be listed on this webpage in the
future. You can choose to go with the name I have currently listed, or
make up your own.
- Abstract You should write a two or three lines summary of
your topic. Feel free to use what I have listed below or make up your
The applet should present and explain your concept or algorithm rather
than just implement something. For example, if your problem was to
compute a convex hull, it would not be very interesting to just show
the convex hull, even if the code used to compute it is very
advanced. It would be much better to have an interface showing how
the algorithm proceeds step by step, allowing the user to play and
experiment. You are even allowed to "cheat" with respect to the
internal implementation. That is, I don't care if the internals of the
applet really use such or such technique, as long as what it shows is
correct and explains well. For example, if an unimportant step of an
algorithm you are demonstrating is to find the closest pair of points
in a point set, I don't mind if, to simplify your implementation, you
use a O(n^2) algorithm even if the algorithm you are demonstrating
runs in O(n log(n)).
The code of your applet must be available to me.
Policy on using existing material
As for any publication, you are allowed to use any material available
as long as you acknowledge any source you use. This is true for your
HTML tutorial as well as for the applet. Don't hesitate to start from
some existing applet to create yours, and to mix and match existing
code from any source. But: you must acknowledge all sources you
use very carefully, and make sure you have the permission to use
them. You also must indicate clearly what your contribution is.
In order for your applet to remain available forever (?), I request that
you install all the necessary files on the servers of the CGM lab (ask
Greg). I also request that you consider releasing the java source of your
applet so that future students can use some of your code in their
future projects, although this is not a requirement. I do however require
that you give me access to your code for grading purposes.