Prof. Micha Sharir (firstname.lastname@example.org)
Fall 2013, Tuesday 15:00-18:00, Kaplun 324
*** Returned assignments are in Schreiber 114 (including Ex. 4) ***
*** Brief solution to assignment 4 is also available now ***
Solution to assignment 4
*** Brief solutions to assignments 1--3 are now available ***
Solution to assignment 1
Solution to assignment 2
Solution to assignment 3
*** Assignment 5 is now available ***
*** Assignment 4, Problem 1(b), has been modified ***
Assignment 1, due November 12, 2013
Assignment 2, due December 3, 2013
Assignment 3, due December 24, 2013
Assignment 4, due January 14, 2014
Assignment 5, due before the exam, in my mailbox, or electronically
Final Exam: An in-class exam, Sunday, 9.2.14, 9:00--12:00.
The exam will be with open material (of any kind).
There will be a choice: Four out of five questions.
The questions will be much more modest than the exercises.
Scanned lecture notes (courtesy of Igor Tubis)
(These notes are not edited. They are given as a service to the students, who should use them accordingly.)
Lecture 1, 15.10.13, scanned notes
Lecture 2, 22.10.13, scanned notes
Lecture 3, 29.10.13, scanned notes
Lecture 4, 5.11.13, scanned notes
Lecture 5, 12.11.13, scanned notes
Lecture 6, 19.11.13, scanned notes
Lecture 7, 26.11.13, scanned notes
Lecture 8, 3.12.13, scanned notes
Lecture 9, 10.12.13, scanned notes
Lecture 10, 17.12.13, scanned notes
Lecture 11, 24.12.13, scanned notes
Lecture 12, 31.12.13, scanned notes
Lecture 13, 7.1.14, scanned notes
Lecture 14, 14.1.14, scanned notes
The course covers various topics in geometric optimization.
The course Computational Geometry is a prerequisite.
Otherwise, by special permission of the teacher.
There is no textbook that covers the material given in the course.
There are several survey papers and other written material that will be distributed during the class.
S. Toledo's M.Sc. Thesis . Chapter 1 is a good source on parametric searching and related techniques.
Agarwal-Sharir's survey on geometric optimization .
Agarwal-Sen's survey on randomized techniques for geometric optimization .
Chan's randomized technique .
Gaertner-Welzl's survey on randomized techniques for linear programming and related problems .
Slides by Agarwal on clustering .
Arora's survey on TSP approximation.
Survey on coresets.
Other Course Material:
A note on Megiddo's 3-dimensional LP algorithm.
The subexponential LP paper by Matousek, Sharir, Welzl.
Agarwal-Procuppiuc' p-center algorithm.
Rectlinear center paper.
Overmars - van Leeuwen paper.
Chan's approximation algorithms.
Paper on width, smallest annulus, etc.
A reminder of the textbooks in computational geometry:
Final exam and a few (four--five) assignments during
Assignments will be graded and will comprise part (about 20 percent) of the final grade.
The syllabus of the course
The syllabus may not exactly coincide with the material that will be taught. It will be (slightly) updated during the semester
(1) Parametric Searching:
(2) Linear Programming: Geometric Approach:
(3) Search in Monotone Matrices:
(4) Facility Location:
(5) Diameter in Three Dimensions:
(6) Geometric Optimization and Arrangements:
(7) Shortest Paths:
(8) Approximation Algorithms for Geometric Optimization:
(9) Approximate Nearest Neighbor Search in Higher Dimensions: