Prof. Micha Sharir  (michas@tau.ac.il)
                                         Fall 2008, Monday 16:00-19:00, Dach Auditorium

Assignment grader: Adam Sheffer sheffera@post.tau.ac.il
Mailbox: Adam's mailbox 318, Schreiber Building, first floor (near the elevator)

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

*** Assignment 5 returned ***
Available in Room 114 Schreiber on one of the shelves

*** SHI'UR KHAZARA ***
THIS TUESDAY, 3.2.09, Schreiber 07, 16--18

*** Here are example solutions

*** Here are solutions to assignments 1--4

*** Here are lecture notes, taken by one of the students
*** The notes are offered as a public service; they are not edited
*** and the "management" is not responsible for their contents...
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 December 1, 2008 (in pdf format)

Assignment 2, due December 15, 2008 (in pdf format)

Assignment 3, due December 29, 2008 (in pdf format)

Assignment 4, due January 19, 2009 (in pdf format)

Assignment 5, due February 9, 2009 (in Adam's mailbox) (in pdf format)

Sarnak-Tarjan paper on persistent search trees

Final Exam: Friday, February 6, 2009

An in-class exam
You may bring to the exam one sheet of paper with anything you want to write on it,
And no other material.
The exam comprises about 80% of the final grade.
GOOD LUCK!!

Moed Bet: Friday, March 6, 2009

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).

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