Prof. Micha Sharir  (michas@tau.ac.il)
                                         Spring 2011, Tuesday 16:00-19:00, Handasa Kitot Bldg., Room 003

Announcements:

There will be Shi'ur Khazara on June 19, 2011, 15:00-18:00 in Schreiber 007

There was NO class on March 15, 2011

There was NO class on April 12, 2011

There were two make-up classes (Shi'urey Hashlama):

Friday, May 13, 9:30-12:30, Kaplun 118

Friday, May 27, 9:30-12:30, Kaplun 118

Assignment grader: Tal Kaminker email: tkaminker@gmail.com

Please address all special requests to Tal, cc'ed to me.

*** Here are brief solutions of assignment 1

*** Here are brief solutions of assignment 2

*** Here are brief solutions of assignment 3

*** Here are lecture notes, taken by one of the students two years ago.
*** The notes are offered as a public service; they are not edited
*** and the "management" is not responsible for their contents...
*** The course this year may slightly deviate from the material presented in these notes!
Lecture 1 (3.11.08)
Lecture 2 (10.11.08)
Lecture 3 (17.11.08)
Lecture 4 (24.11.08)
Lecture 5 (1.12.08)
Lecture 5--different version (1.12.08)
Lecture 6 (8.12.08)
Lecture 7 (15.12.08)
Lecture 8 (22.12.08)
Lecture 9 (29.12.08)
Lecture 10 (5.1.09)
Lecture 10 (partial) (5.1.09)
Lecture 11 (12.1.09)
Lecture 12 (19.1.09)
Lecture 13 (26.1.09)

*** By popular demand, here are links to two past (take-home) exams:
Exam 1
Exam 2

Assignments:

5 assignments will be given. They comprise about 20% of the final grade.

Assignment 1, due March 22, 2011

Assignment 2, due April 5, 2011

Assignment 3, due May 17, 2011

Assignment 4, due May 31, 2011

Assignment 5, due June 19, 2011

Sarnak-Tarjan paper on persistent search trees

Final Exam: Tuesday, June 21, 2011

An in-class exam
You may bring to the exam any written material
The exam comprises 80% of the final grade.
GOOD LUCK!!

Moed Bet: October 24, 2011

Course description

The course is a basic course in computational geometry. It assumes basic knowledge in algorithms, data structures, complexity, etc.
Basic knowledge of probability is also needed.
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 (1997); second edition (2000)
(there is also a recent third edition).

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

• Preparata and Shamos, 
  Computational Geometry, An Introduction (1985)
  (the first textbook on the subject, rather outdated)
• Edelsbrunner, 
  Algorithms in Combinatorial Geometry (1987)
  (another old and slightly more advanced textbook)
• Mehlhorn, 
  Data Structures and Algorithms, 3: Multidimensional Searching and Computational Geometry (1983)
  (oldest book, not easy to read)
• Mulmuley, 
  Computational Geometry: An Introduction Through Randomized Algorithms} (1993)
  (uses very special approach)
• O'Rourke, 
  Computational Geometry in C (1994)
  (elementary, practically oriented; has lots of code)
• Boissonnat and Yvinec, 
  Algorithmic Geometry (1998)
  (another `modern' textbook)

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

The syllabus of the course

(1) Introduction:

• Motivation, Goals, Models of Computations

(2) Convex Hull Algorithms:

• Properties of convex sets and convex hulls
• Simple-minded algorithms: Gift wrapping
• Graham's Walk; analysis
• Divide-and-Conquer approaches
• Average case behavior
• Applications of convex hulls: width; diameter; normal diagram
• Convex hulls in higher dimensions
• Convex polyhedra, Euler's formula, polyhedra in 3-D
• On the size of convex hulls in higher dimensions; general bounds
• Planar maps; the DCEL data structure
• Randomized convex hull algorithms
• Lower bounds

(3) The Sweeping Paradigm:

• An example: Detecting/Reporting intersections among n line segments
• Other examples: Intersection of other classes of objects
• Vertical adjacency of line segments
• Nearest neighbors
• Batch point location inside/outside a simple polygon
• Planar maps
• Overlaying planar maps and its applications

(4) Point Location:

• Problem definition
• General parameters: Preprocessing, Space, Query time
• Naive solution using sweeping (good for batch problems)
• Kirkpatrick's hierarchical method
• Persistent search trees
• Seidel's randomized method

(5) Intersection Problems and Linear Programming:

• Duality
• Intersection of n half-planes; dual formulation as a convex hull problem; divide and conquer approach
• Intersection of n half-spaces; dual formulation
• Linear Programming in two and three dimensions in linear time; related problems
• Applications

(6) Voronoi Diagrams:

• Nearest neighbor searching problems
• Voronoi diagrams: definitions and basic properties
• Delaunay triangulation
• Calculation of the diagram for a set of points
• Randomized incremental construction
• Lower bounds
• Applications: nearest neighbor searching; post-office problem; Euclidean minimum spanning trees; triangulation; motion planning for a disk
• Fortune's line-sweeping algorithm
• Yap's algorithm for line segments
• k-nearest neighbor diagrams; diagrams in higher dimensions

(7) Range Queries and Multidimensional Data Structures:

• Two-dimensional rectangular range queries. The range, segment, and interval trees. Other solutions
• Dynamization of data structures
• Applications to problems involving iso-oriented rectangles
• Higher-dimensional rectangular queries and intersection detection
• Half plane range queries and the ham sandwich theorem
• Generalizations to higher dimensions and more complex queries