Search
Close this search box.

Computational Geometry, Fall 2020–2021

0368-3173-01

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

Recitation: Wednesday, 18:10-19:00

Location: Zoom

Office hours: by appointment; we can have zoom sessions, meet in my office (CheckPoint 434), or correspond by email
Teaching Assistant: Michal Kleinbort, [email protected]

Grader: Tomer Even, [email protected]

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, traditional style
Exam(ple), pdf file, new covid-19 style; example first page of answers, 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 [pdf], due: November 9th, 2020
  • Assignment no. 2 [pdf], due: November 23rd, 2020
  • Programming assignment [pdf], due: January 17th, 2021, 23:59; see additional information
  • Assignment no. 3 [pdf], due: December 14th, 2020
  • Assignment no. 4 [pdf], due: January 4th, 2021
  • Assignment no. 5 [[[pdf], optional; if you wish to have your assignment checked, submit by January 14th, 2021

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:
Orthogonal range searching II, continuedNearest-neighbor search using kd-trees (Slides)
Motion planning and the connection to NN search (Slides)

14.12.20:
Trapezoidal maps and planar point location (CGAA, Chapter 6, slides6)

Guaranteed logarithmic-time point location (slides, paper)

21.12.20:
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)

28.12.20:
Voronoi diagrams (CGAA, Chapter 7, slides7_combined)

04.01.21:
Voronoi diagrams continued: Arcs on the beach line (slides)

Triangulating planar point sets and Delaunay triangulations (CGAA, Chapter 9) (slides)

11.01.21:
Connections between major geometric structures (slides)

Extra, which we did not cover in class: Computing convex hulls in 3D (CGAA, Chapter 11) (slides)

Programming Assignment, Additional Information

Submission

Please provide an archive that contains all source and documentation files in a flat directory structure (that is, place all files in one directory); Use Moodle to submit the file. Do not forget to state your names and IDs.

You may develop your code in C++, Java or in Python.

You may send questions about the exercise to Dr. Efi Fogel via email ([email protected]).

General

Both input files and your generated solution files need to conform with the format used in the SG:SHOP 2021 challenge.
See the link here
You may find the provided Python-based utility library useful: link

Solution verification and visualization

You are provided a python program to verify and visualize your solutions.
Robots are visualized as squares of different colors.
Targets are visualized as square boundaries, each colored with the color of the respective robot that should reach the target.
Obstacles are visualized as gray squares.
The program (simulation.py) has two input fields:
  1. The path to the file that contains the description of the scene. If filled, click on “initialize” to view the scene. You can zoom in and out using the + and – keys on your keyboard, respectively.
  2. The path to the file that contains a solution to the scene. If filled, after initializing click on “run” to visualize and verify your solution.
How to run the program:
1. Download the program files: [link]
2. Install Python 3
3. The program requires the installation of PyQt5 (pip install PyQt5).
4. On Linux you may need to install libxcb-xinerama0 (sudo apt-get install libxcb-xinerama0).
5. Install numpy (pip install numpy)
6. Install colour (pip install colour)
7. Run simulation.py

Optimal solver for the case of a single robot

Additionally, you are provided a python script that given an instance with only one robot outputs an optimal solution.
The program (1_robot_solver.py) accepts 2 arguments:
  1. The path to the file that contains the description of the scene.
  2. The path to the file where the solution will be saved.
How to run the program:
1. Install Python 3
2. Install numpy (pip install numpy)
3. Install networkx (pip install networkx)
4. Run 1_robot_solver.py with the command line arguments described above

Books

The main textbook used in the course:

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry: Algorithms and Applications , 3rd Edition
Springer, 2008.

J. O’Rourke,
Computational Geometry in C , 2nd Edition
Cambridge University Press, 1998 

J.-D. Boissonnat and M. Yvinec
Algorithmic Geometry
Cambridge University Press, 1995, 1998 (English version)
J.E. Goodman , J. O’Rourke, and Csaba Toth (editors) 
Handbook of Discrete and Computational Geometry , 3rd Edition
CRC Press LLC, Boca Raton, FL, 2017.
J.-R. Sack and J. Urrutia (editors)
Handbook of Computational Geometry
North Holland, 2000.
M. Sharir and P.K. Agarwal
Davenport-Schinzel Sequences and Their Geometric Applications
Cambridge University Press, New York, 1995
K. Mulmuley
Computational Geometry: An Introduction Through Randomized Algorithms
Prentice Hall, Englewood Cliffs, NJ, 1994
F.P. Preparata and M.I. Shamos
Computational Geometry: An Introduction
Springer-Verlag, New York, NY, 1985.
H. Edelsbrunner
Algorithms in Combinatorial Geometry Springer Verlag, Heidelberg, 1987.

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content