Prof. Micha Sharir  (michas@tau.ac.il)
                                         Spring 2015, Monday 15:00-18:00, Orenstein 102

Announcements:

*** By popular demand, here are links to two past in-class exams:
Exam 1
Exam 2

Shi'ur khazara: Sunday, 21.6, 15--, Schreiber 309

Assignment 3 can be picked up from a shelf near the "open space" in the basement

The class in 18.5 is cancelled.

Make-up class will be given on Friday, 29.5, 10--13, in Schreiber 008

Assignment grader: Omer Gold email: omergold@post.tau.ac.il

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

Solution sketches (so far for assignments 1 and 2)

brief solutions of assignment 1

brief solutions of assignment 2

brief solutions of assignment 3

brief solutions of assignment 4

brief solutions of assignment 5

*** Here are lecture notes, taken by one of the students six 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 April 13, 2015

Assignment 2, due May 4, 2015

Assignment 3, due May 29, 2015

Assignment 4, due June 15, 2015

Assignment 5, due June 29, 2015 (in Omer's mailbox or by email to him)

Expected size of the convex hull of random points

Sarnak-Tarjan paper on persistent search trees

Final Exam: Moed Alef: June 23, 2015

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: July 24, 2015

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)
third edition (2008)

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 in-class 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