Spring 2020, 0368-3173-01

**Lecture**: Monday, 16:00-19:00, Schreiber 006

**Instructor**: Dan Halperin , danha@post

**Grader**: Yair Karin, Golan Miglioli-Levy

The course covers fundamental algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, Voronoi diagrams, polygon triangulation, and linear programming in low dimensional space. We will also discuss several applications of geometric algorithms to solving problems in robotics, GIS (geographic information systems), computer graphics, and more.

**Bibliography**

The main textbook of the course is:

*Computational Geometry: Algorithms and Applications *(CGAA), 3rd edition by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.

A bibliographic list for the course

### Slides

I will often use slides that accompany the main textbook of the course.The slides are by Marc van Kreveld and they can be found

at the following site: Geometric Algorithms

### Assignments, Examination and Grade

The standard assignments will account for 10% of the final grade, in case they improve the final grade.

The grade in the final exam will account for the remaining 90% of the grade in the course.

Exam(ple) [pdf]

Although the assignment grades will be used only for improving the final grade, submission of the assignments is mandatory and a prerequisite for taking the exam.

About halfway through the course (probably earlier), we will present a **programming assignment**.

More details on the assignment will be provided later.

We encourage you to submit the programming assignment as well. This is not mandatory.

If however you do submit it, then your grade breakdown will be 10% the standard assignments,

15% the programming assignment, and 75% the final exam. Here as well,

the assignments grades will be counted toward the final grade only if they improve it.

The assignments will appear here.

- Assignment no. 1 file , due: April 5th, 2020.
- Assignment no. 2 file , due: April 20th, 2020.
- Assignment no. 3 file , due: May 11th, 2020.
- Assignment no. 4 file , due: June 1st, 2020.
- Programming assignment (optional) file (revised 21/5/20, notice the order of cosine,sine), due: June 18th, 2020. Additional information
- Assignment no. 5 (optional) file , due: June 24th, 2020.

### Course Summary

Below you’ll find a very brief summary of what was covered in class during the semester.

This should not be taken as a complete description of the course’s contents.

**09.03.20**What is Computational Geometry?

Course outline, motivation and techniques. A slow convex hull algorithm. Orientation (Side-of-line) test. (slides1, up till Slide #27.)**16.03.20 (online)**The Doubly Connected Edge List, DCEL, and map overlay (CGAA, Chapter 2). (slides2b)Euler’s formula for plane graphs, proof without induction (Proofs from THE BOOK, Aigner-Ziegler, 5th Ed., Chapter 13)

**23.03.20 (online)**Point-Line duality, arrangements of lines in the plane, the zone theorem and incremental construction of the arrangement (CGAA, Chapter 8). Applying all this to solve collinearity, and to sum of squares of face complexities.

**30.03.20 (online)**Polygon triangulation and the art gallery problem (Slides)

**20.04.20 (online)**Casting, half-plane intersection and Linear Programming in low dimensions (slides4a).Supplementary material: unbounded LP2D and more (Slides, revised 23.04.20).

**27.04.20 (online, 2 hours)**

LP in 3D.Smallest enclosing circle (CGAA Section 4.7, slides4b). GeoGebra files: SEC is unique, SEC new point on boundary

**04.05.20 (online)**Point-Line duality, arrangements of lines in the plane, the zone theorem and incremental construction of the arrangement (CGAA, Chapter 8) (slides8).

More on arrangements and duality (slides).

The minimum area triangle problem (CGAL Arrangements and Their Applications, Section 4.2.1)**11.05.20 (online):**Orthogonal range searching I: kd-trees (CGAA, Chapter 5)(slides5a)CGAL: An overview (Slides)

**18.05.20 (online):**

Orthogonal range searching II: kd-trees (cont’d), range trees, fractional cascading, handling degeneracies through composite numbers (CGAA, Chapter 5)(slides5b)**25.05.20 (online):**Trapezoidal maps and planar point location (CGAA, Chapter 6) (slides6, up till Slide #56)Nearest-neighbor search using kd-trees (Slides)Nearest-neighbor search in robot motion planning (Slides)

**01.06.20 (online):**

Trapezoidal maps and planar point location, cont’d (CGAA, Chapter 6) (slides6)Guaranteed logarithmic-time point location (slides, paper)Voronoi diagrams of points in the plane: structure, complexity, and Fortune’s algorithm (CGAA, Chapter 7) (slides7_combined)**08.06.20 (online):**

Voronoi diagrams, continued (CGAA, Chapter 7) (slides7_combined)Arcs on the beach line (slides)Triangulating planar point sets and Delaunay triangulations (CGAA, Chapter 9) (slides)Alpha shapes, a glimpse (slides9, Slides #60-67), in 3D: paper by Edelsbrunner and Mucke**15.06.20 (online):**

Connections between major geometric structures (slides)Computing convex hulls in 3D (CGAA, Chapter 11) (slides)22.06.20 (online)

The casting problem revisited (slides) (paper)