Computational Geometry and Applications
Fall, 1999

Dr. Klara kedem

**** IMPORTANT NEW ANNOUNCEMENT 27.1.2000 !!!!***
MOED ALEF solution Exam grades will hang on my door after 14:00

Course Description
Computational Geometry is the study of algorithms for solving geometric problems. The core of the field consists of a set of techniques for the design and analysis of such algorithms. It has deep connections to classical mathematics, theoretical computer science, and practical applications, that arise, e.g., in areas like statistics, computer vision, graphics, engineering, and more. The problems dealt with are typically posed as queries on sets of geometric objects, such as points, segments and polygons in the plane, or points, segments and polytopes in higher dimensions.

Tentative Scope of the Course
In this course we will cover lines' and polygons' intersection problems, convex hulls, point location and range queries, proximity problems (Voronoi diagrams and Delaunay triangulations) and geometric optimization. We will study a variety of techniques, such as the sweepline paradigm, divide and conquer, and randomized algorithms. We will learn some geometric data structures. We will deal with applications of computational geometry to image matching, collision free robot's motion planning, and more.

Homeworks and grading:
There will be up to 6 written homeworks assignments - for a total of 18 grade points.
1-2 class summaries on the web - will give you 10 grade points.
Final exam - 72 grade points.

Textbooks:
The course textbook is ``Computational Geometry: Algorithms and Applications'', by M. de Berg, M. van Kreveld,M. Overmars and O. Schwarzkopf, Springer-Verlag, 1997.

Other books that cover some of the topics:

• [CLR] Cormen, Leiserson and Rivest, ``Introduction to Algorithms'', MIT Press, 1991.

• [Me] K. Mehlhorn, ``Data Structures and Algorithms 3:Multi-dimensional Searching and Computational
  geometry'', Springer-Verlag, 1984.

• [OR] J. O'Rourke, ``Computational Geometry in C'', Springer-Verlag, 1994.

• [PS] F. Preparata and M.I. Shamos, ``Computational Geometry'', Springer-Verlag, 1988.

• [Ke] K. Kedem, ``The Open University learning guide for Computational geometry''.
  
  

Office hours:
Monday 16:00-17:00

Announcements:

• 20.1.2000
  Test sample is downloadable in the last line of the schedule. A hard copy can be found in Oren's office.

• 11.1.2000
  -- Homework number 5 can be picked in Oren's office
  --You may xerox a solution of HW5 from a copy in Oren's office.

• 6.1.2000
  --The course is finsihed - there will be NO CLASSES on January 10 and 12.
  --There will be a review class on Monday, January 24,2000 at 18:00,
  in room 147, bldg 72
  --Please find out on this web page or on the board, the location of the room.

• New weights on homeworks
  --You will be asked in the exam if you want the homework assignments to weight 18 points or 30 points. Your written decision will be irreversible for that term!

• 8.11.99
  --Submission of HW2 was postponed till 15.11.99
  --You may xerox a solution of HW1 from a copy in Oren's office.
  --We will meet from now on on Wednesdays in 209/32 from 2-4
  

Schedule+homeworks+class summaries