Computational Geometry
      G22.3033-009
 

                                           Prof. Micha Sharir  (sharir@cims.nyu.edu)
                                                                    Fall 2000, Wed 7-9 pm; Room: 102 =====

=====

The course is a basic course in computational geometry. It assumes basic knowledge in algorithms, data structures, complexity, etc. It also assumes familiarity with basic geometric concepts and facts (in the plane and in higher dimensions).

There is no textbook that covers all the material given in the course, but a large portion of it is covered in the book:

De Berg, van Kreveld, Overmars and Schwarzkopf,
Computational Geometry, Algorithms and Applications (1st edition: 1997; 2nd edition: 2000).

Additional material will be distributed or given a reference to, as needed.
One may also consult the books

Course requirements: Final exam and a few (about four--five) assignments during the semester. Assignments will be graded and will comprise part (about 20 percent) of the final grade. -----

The syllabus of the course -----

(1) Introduction:

-----

(2) Convex Hull Algorithms:

-----

(3) The Sweeping Paradigm:

-----

(4) Point Location:

-----

(5) Intersection Problems and Linear Programming:

-----

(6) Voronoi Diagrams:

-----

(7) Range Queries and Multidimensional Data Structures:

-----