274 Computational Geometry
Computational Geometry is a branch of Theoretical Computer Science
which seeks good solutions ("algorithms") for computational problems with
a geometrical flavor. The problems may come from a variety of applied
fields, such as Computer Graphics, Computer Animation, Robotics,
Computer Vision, Geographical and Spatial Databases, medical applications
such as Tomography, etc. But it is not the applications that we seek here:
we look for the underlying abstract structure, strip off
(most of the) implementation-dependent details and search for a general,
efficient algorithmic solution.
This is NOT a programming intensive
course. In fact, there MAY be very little programming in this
class. I like to adjust some components of the course to the
particular interests of the students taking it, so if people
would like to do and see implementations of geometric algorithms
and/or implementation-related topics,
then I will spend considerably more time
with them. Otherwise, most of the class will be devoted to algorithms and
their underlying theory, and the weekly
homework will consist of small problem sets.
After the first introductory half of the semester, the students will choose a
problem to research on. The requirement will be that they either
do individual reading of material related to the chosen topic
(typically
a book chapter and library/database search for related papers),
or that they will do an implementation of an algorithm.
The research project will be presented in class in the last week
of the semester and a paper or web page describing it will be
submitted before the exam period.
There will be two lectures per week, and the third lecture slot
will be used, at the
discretion of the professor, for:
- Discussion of problem sets/homework.
- Student presentations and discussions of problems and
progress with the final project (second part of the semester)
- Lectures given by a few outside speakers.
Contents
- Art Gallery Problems. Visibility.
- Triangulations.
- Convex Hulls in dimension 2 and 3.
- Arrangements of lines. Duality.
- Proximity: Voronoi diagrams and Delauney triangulations.
- Visibility graphs and shortest path problems.
- Geometric software.
- Applications.
- LEDA: a C++ Library of Efficient Algorithms and Data Structures.
Back to the
class home page
Spring 2000, at
http://cs.smith.edu/~streinu/Teaching/Courses/274/home.html