70240183 (Fall 2001): Syllabus
-1+2*(2!+3!)!*(4!+5!+6!+7)+7*7*7*8 = 70240183
-0!+1234+5!-(6-78)*9 = 2001
-
Lectures
-
Sep. 13, 2001- Jan. 10, 2002
-
Thursday(9:50-12:15)/week
-
Building III, 1301
-
Introduction
-
People see "Computational Geometry
(CG)" quite differently in various circumstances. For those studying curves and
surfaces, it is an alternative for Geometric Modeling. Many chapters on Data
Structure are titled "Computational Geometry". These authors understand CG as
intuitive analysis on Graph Theory or Searching Theory. Shamos' thesis in 1978
is regarded widely as the beginning of modern CG. Since then, this phrase
has been used to refer to algorithmic study on discrete and combinatorial
geometric structures. Although many researchers in this area restrict CG only to
the planar structures, I intend to interpret it in a rather broad sense that CG
covers multi-dimensional problems also.
-
CG is the daughter of Euclidean
geometry, combinatorics, graph theory, optimization theory, and analysis of
algorithms. Although she has just past her twenty, almost all areas in Computer
Science have benefited greatly from her. Among them are computer graphics,
geometric modeling, computer vision, robotics, and image processing.
-
Most computational geometers believe
that the essence of CG, as Computer Science itself, is constructive. Hence
current CG closes its door against problems which are unconstructive in Turing
model. Seeing the dawn of new computational models such as Quantum Computer, we
can hope them to become members of the CG family.
-
Course Objectives
-
I set three objectives.
-
1. A general awareness of CG theory.
-
The indicator of success is that
students would like to think more from the point of CG while doing their future
research.
-
2. Fundamental concepts and
techniques of CG.
-
These include arrangement /
configuration, convex hull, Voronoi diagram, decomposition / triangulation,
visibility graph, geometric intersection / searching / optimization, etc.
-
3. The ability to solve real problems
with CG algorithms.
-
This ability is more essential than
that of just to learn theories from books. Hence, as the most important criteria
of the evaluation, each student will conduct a project by implementing at least
one algorithm for a real problem.
-
Textbooks & Further Readings
-
Although students may feel that my lecture notes are rich enough, they are still
encouraged to read more books.
-
[PS85]
Computational Geometry: An Introduction, by F. P. Preparata & M. I. Shamos,
Springer-Verlag, 1985.
-
[Or98]
Computational Geometry in C, J. O’Rourke, 2nd edition, Cambridge University
Press, Cambridge, 1998.
-
[GR97] Handbook
of Discrete and Computational Geometry, Goodman and O'Rourke (eds), CRC
Press LLC, Boca Raton, FL, 1997.
-
[Mul94]
Computational Geometry: An Introduction Through Randomized Algorithms, by
Ketan Mulmuley, Prentice Hall, 1994.
-
[PAW95]
Combinatorial Geometry, by J. Pach and P. K. Agarwal, J. Wiley, New York,
1995.
-
[Ed87]
Algorithms in Combinatorial Geometry, Herbert Edelsbrunner, Springer-Verlag,
1987.
-
[Or87] Art
Gallery Theorems and Algorithms, J. O’Rourke, Oxford University Press, 1987.
-
[SA95]
Davenport-Schinzel Sequences and Their Geometric Applications, by Sharir and
Agarwal, Cambridge University Press, 1995 (ISBN: 0521470250).
-
[La96]
Computational Geometry in C++, by Laszlo, Prentice-Hall, 1996 (ISBN
0-13-290842-5).
-
[BKOS00]
Computational Geometry: Algorithms and Applications, by de Berg, van Kreveld,
Overmars, and Schwarzkopf, 2nd edition, Springer-Verlag, 2000 (ISBN:
3-540-65620-0).
-
[DM98]
Algorithmic Geometry, Boissonnat, by Jean-Daniel and Yvinec, Mariette,
Cambridge University Press, March 1998 (ISBN: 0-521-56322-4).
-
[Me84] Data
Structures and Efficient Algorithms 3: Multi-dimensional Searching and
Computational Geometry, by Kurt Mehlhorn, EATCS Monographs in Computer
Science 3, Springer-Verlag, 1984.
-
[周00]
计算几何，周培德，2000年3月第一版，清华大学出版社.
-
Homework Assignment
-
A new homework assignment can be
downloaded from the course page at the end of each chapter. Please hand your
solutions in before the due date (typically, you have 2~3 weeks).
-
Each task is assigned with different
number of points according to the difficulty. Students do not have to finish all
of them. The points you gain will be accumulated before reaching the maximum 30.
-
Collaboration among no more than 3
students is permitted providing that all authors are declared. In case of 2
students, each will receive ë2/3û of the full points, and 3 students each ë1/2û.
In case of more than 4 students, all will receive zero.
-
A plagiarist will receive zero for
his/her homework. Furthermore, the stolen points will be subtracted from his/her
final score.
-
Project
-
Each project should be
conducted by exactly 3 students sharing similar interests on CG. All members of
a group will receive a same number of points. (So, collaboration is of most
importance here.)
-
Each project group
should write a project proposal before the 10th Sunday (Nov. 18,
2001).
-
Projects should be
checked before the 18th Sunday (Jan. 13, 2002).
-
Each project group
should write a project report before the 18th Sunday (Jan. 13, 2002).
-
Important Date
-
Nov. 18, 2001 Hand in your project proposal
-
Jan. 13, 2002 Evaluate your project and hand in the final report
|