HOME ] UP ] [ Syllabus ] Bulletin ] Handout ] Evaluation ]


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.

  • Prerequisites

    • Algorithm Design / Programming

    • Data Structure

    • Algorithm Analysis

  • What You Will Learn

    • Convex hull

    • (Delaunay) triangulation

    • Voronoi diagram

    • (Planar) arrangement

    • (Planar) configuration / dissection

    • Intersection

    • (Planar) point location

    • (Planar) range search

    • Transversal

  • 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月第一版,清华大学出版社.

  • Evaluation Policy

    • The final grades will be based on quiz/discussion(0~10), homework assignment(30), and the project(70).

  • 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


TOP

HOME ] UP ] [ Syllabus ] Bulletin ] Handout ] Evaluation ]

Copyleft (c) 2003-3002, Junhui Deng
Last updated on 05.30.2012