COMP 584: Computational Geometry Fall 2000

Announcements

Tue Aug 15 15:17
It is unclear if this class will be taught this semester.

See at the bottom of the page for old announcements.

There is an abundance of material in this field and we will not be able to cover everything. The goal of this class is to give you a general intuition for computational geometry and to familiarize you with the most commonly used techniques. Rather than casting the material in terms of their potential applications (as it is done in the textbook), I would like to stress the aspect of an "intellectual tool box." The content of this class should not only enable you to write a faster ray tracer, but also to understand and solve a wider range of problems involving aspects of geometry.

In addition you will explore some aspects of academic work, like literature research, summarizing the state of the art, and presenting the results in a presentation. Much of this is what academics is about: to understand the problems, know existing approaches to solve them, and come up with your own (hopefully better). Once you have accomplished that you would write it up in a paper and publish it in a journal or at a conference, where you would have to give a presentation on your research. The second part of this class is supposed to give you a feel for this kind of work: you will research a certain topic in computational geometry, summarize the state of the art, and present your findings in class.

The pace of the class will be determined as we go along. If there is interest we will dive deeper into the details. Here's a tentative list of topics:

• Arrangements (of lines)
• Proximity problems: Voronoi diagrams and Delaunay triangulations
• Convexity: computing the convex hull
• Geometric searching: point location, range search
• Randomized techniques
• Visibility and shortest path problems
• Computational issues: primitives, models, bounds, robustness, ...

In addition, students in the class will generate lecture notes. References to journal papers or otherwise published material will be provided for further reading.

• Any topic from the lectures in more depth
• Biochemical/molecular modeling
• Collision detection
• Combinatorial geometry
• Kinetic data structures
• Sphere packing
• Tiling
• Triangulations
• Power diagrams
• Randomized techniques
• Your suggestion here

• Two homeworks with four problems each. You are required to solve two problems from each homework. The problems will be challenging. (40%)
• A presentation given on an advanced topic in computational geometry, based of several publications in the field. This presentation is an important part of this class. You will be required to perform literature research, present the material in class, and write a short summary of the (40%)
• Two write-ups of the material presented in class. (20%)

Tue May 23 13:05
Here you will find the latest announcements.