### Teachings

Select Academic Year:     2017/2018 2018/2019 2019/2020 2020/2021 2021/2022 2022/2023
Professor
RICCARDO SCATENI (Tit.)
Period
First Semester
Teaching style
Convenzionale
Lingua Insegnamento
INGLESE

Informazioni aggiuntive

Course Curriculum CFU Length(h)
[60/73]  INFORMATICS [73/00 - Ord. 2017]  PERCORSO COMUNE 9 72

### Objectives

Knowledge and understanding:

• Know the main algorithms used to solve problems modeled using simple tools of Euclidean geometry in the plane and space
• Know what they are and how to use the data structures for the description of geometric entities in the plane and space
• Understand the classification of the paradigms that guide the design of algorithms (geometric and not) by distinguishing the various types of algorithms used

Applying knowledge and understanding:

• Being able to make an accurate empirical evaluation of computational complexity (both in time and in space) of the algorithms studied
• Design and implement an interactive application based on one of the algorithms seen during the course
• Use, in an advanced way, software development tools based on the C++ language

Making judgments

• Develop independently, concerning the design and implementation choices, the final project from the specifications provided

Communication skills

• Understand, summarize and expose a scientific text, written in English, treating in-depth one of the topics covered during the course

Learning skills

• Use multiple sources to solve the exercises assigned as homework

### Prerequisites

It is essential to have basic knowledge of:

Geometry (plane and space)
Calculus
Linear algebra (vectors and matrices man)

Courses of the first tier program in Informatics partially treating the basic knowledge required are:
Matematica discreta (Discrete Mathematics)
Algoritmi e strutture dati (Algorithms and Data Structures)

### Contents

Numbers in brackets refer to chapters and sections of the textbook:

• Convex hull [1]
• Line intersection [2]
• Polygons triangulation [3]
• Geometric search [5]
• Point map problem [6]
• Voronoi diagrams [7]
• Delaunay triangulation [8.{1-3}]
• Other geometric data structures [10]
• BSP trees [12]
• 3D convex hull [11]

### Teaching Methods

56 hours of lectures, 16 hours of an interactive and cooperative design of algorithms (interlaced during the course).

### Verification of learning

Six tasks contribute to the final vote:

One written test in the class where the student should apply known algorithms to sets of data given as input
Two written homework where the student should develop algorithms similar to the ones seen during the lectures
One final-term project which will implement a known algorithm using known data structures
One seminar presenting the contents of a scientific paper
One written report describing the content of the paper

The first three written tasks and the project contribute, each, for 20% of the final grade. They are marked from 0 to 30.

The seminar and the report, marked from 0 to 30, contribute 10% each to the final grade.

Homework will be back no earlier than two weeks after the assignment. Returning the homework beyond the deadline results in a penalty of 2 points on its mark.

The project should be returned by May 31st, after the deadline there will be a penalty of 1 point on the mark for every month of delay up to a maximum of 5 points.

It is not mandatory to take all the tests to pass the exam. When the weighted sum of the votes exceeds the score of 18, the student can ask to verbalize the exam.

### Texts

de Berg, van Kreveld, Overmars, Schwarzkopf
"Computational Geometry, Algorithms and Applications"
Third edition (March 2008)
Springer