Fundamental techniques, data structures, and algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, the Voronoi diagram and Delaunay triangulation of a point set, polygon triangulation, range search, linear programming, point location, in spaces of any dimension. Some topics of Discrete Geometry are also covered (e.g., the crossing number of a graph).
(9.7.01) A 2nd-chance quiz will take place on Sunday 22/7 9am at T-8.
(25.6.01) Project information (summary of an e-mail message): (a) Let me know your final singleton/pair decisions. (b) Submission date: 15/7/01. Approach me for extensions. (c) Software invocation: Singletons: % str-skl in-file.dat out-file.m ; Pairs: % interpol in-file-1.dat in-file-2.dat out-file.m . (d) Software structure: Separate algorithmics from i/o.
(11.6.01) Data files for the project are now available (follow this link). Start with reading the file files/_file_formats.
(29.5.01) Ex3 is now available through this web page.
(16.5.01) Ex2 is now available through this web page.
(8.5.01) Disregard the previous note. There will be a lecture on Thursday 17/5.
(6.5.01) The lecture of Thursday 17/5 is canceled.
(16.4.01) Please start to team up in singletons or pairs for the project. We will start dealing with it next week.
(15.4.01) Those who have not registered yet to the course mailing list are requested to do that before the due date of ex1.
(4.4.01) There will be no lectures on Thursday 19/4 (Holocaust day, no studies 12:30-2:30) and Thursday 26/4 (Independence day). I will be away on Thursday 3/5 (Miluim) and Thursday 7/6 (trip). Maybe my TA will give one of these lectures; details will follow. Two compensation lectures will be given on Sunday 22/4 and on Sunday 6/5, both at 4:30pm in Taub 4.
(3.4.01) ex1 is posted in the course web page.
(14.3.01) The lecture of Thursday 22/3/01 is canceled. A compensation lecture will be given on Sunday 15/4/01 16:30 in Taub 4.
(14.3.01) Note the set up grading policy.
(28.2.01) The easiest way to get into the course e-mail list is by requesting this from me by E-mail. Please also mention your id #, faculty, and toward which degree you are studying.
Main text book:
Computational Geometry: Algorithms and Applications,
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Springer, 1997.
For background:
Computational Geometry in C,
J. O'Rourke,
Cambridge University Press.
Assignments: 30% (submission in singletons!!);
Midterm exam (Takef): 30-35% (Sunday 10/6/01 16:30 in T-9);
Project: 35-40% (programming assignment, course
recognized as a project).
Assignment 1: given 5/4/01, due 19/4/01.
Assignment 2: given 17/5/01, due 31/5/01.
Assignment 3: given 31/5/01, due 21/6/01.