Personal tools
You are here: Home Courses Computational Geometry Fall 2020-2021 Computational Geometry - Fall 2020-2021
« December 2020 »
December
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Computational Geometry - Fall 2020-2021

Fall 2020-2021

0368-3173-01

Course hours: Monday, 16:10-19:00

Recitation: Wednesday, 18:10-19:00

Location: Zoom

InstructorDan Halperin , danha@tauex.tau.ac.il
 
Office hours: by appointment; we can have zoom sessions, 
meet in my office (CheckPoint 434), or correspond by email
  
Teaching Assistant: Michal Kleinbort, balasmic@post.tau.ac.il
 

Grader: Tomer Even, tomereven@mail.tau.ac.il

 


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 file

 
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.

This year's programming assignment is Multi Robot Coordination as described in the Computational Geometry Challenge 2021. We will use the same input and output format. More details on the assignment will be provided soon.

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: November 9th, 2020.

 Assignment no. 2 file , due: November 23rd, 2020.

 Programming assignment (pdf file), due: January 17th, 2021, 23:59; see additional information.

 Assignment no. 3 file , due: December 14th, 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.
For an outline of the course, see for example, the course summary in the Spring 2020 computational geometry course.

 

19.10.20
What is Computational Geometry? 
Motivation and techniques. A slow convex hull algorithm. Graham's O(n log n) algorithm (Chapter 1 in CGAA). (slides1.) Lower bound. Gift-wrapping algorithm for computing the convex hull, Jarvis's March (Preparata-Shamos, Section 3.3.3).
Orientation (Side-of-line) test, course mechanics and overview (slides).
26.10.20
Output sensitive algorithm to compute the intersections of line segments: Bentley Ottmann's plane sweep (CGAA, Chapter 2), (slides2a).
The complexity of a 3D convex polyhedron with n vertices (CGAA, Section 11.1); the last slides of this presentation.
02.11.20
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)
On the complexity of a convex polytope (CGAA, Section 11.1).
The Douglas-Peucker algorithm (see, e.g., wikipedia).
09.11.20
Polygon triangulation and the art gallery problem (Slides)
16.11.20
Casting, half-plane intersection and Linear Programming in low dimensions (CGAA Chapter 4, slides4a).
Supplementary material(Slides), up till Unbounded LP.
23.11.20
Unbounded LP2D, LP3D (Slides).
Smallest enclosing circle (CGAA Section 4.7, slides4b). GeoGebra files: SEC is unique, SEC new point on boundary 
30.11.20
Orthogonal range searching I: kd-trees (CGAA, Chapter 5, slides5a)
Orthogonal range searching II: range trees, fractional cascading, handling degeneracies through composite numbers (CGAA, Chapter 5, slides5b--up till Slide 26)
07.12.20
The plan:
Orthogonal range searching II, continued
Trapezoidal maps and planar point location (CGAA, Chapter 6, slides6)

Document Actions