KIIS COLLOQUIA - MOD 3

This short course offers a gentle introduction to the field of Computational Geometry, a discipline devoted to the design of efficient algorithms for problems involving geometric inputs and outputs. Born in the '70s with the rapid advance of computer graphics and CAD/CAM, computational geometry finds nowadays important applications in fields like Robotics, GIS, Integrated Circuit Design and Computer Vision.
We will start with an overview of Affine and Euclidean geometry that will serve as a basis for a selected list of topics including convex hulls, line segment intersections, orthogonal range searching, polygon triangulations, and trapezoidal maps.
Lectures will be enriched with practical examples and discussions of possible real-world applications.

After the course, the students will be able to:
- Understand the basics of Affine and Euclidean geometry
- Understand and implement all the algorithms discussed along the course

- Linear algebra
- C/C++ programming languages

- Affine and Euclidean geometry
- Convex hulls
- Line segment intersections
- Orthogonal range searching
- Polygon triangulations
- Trapezoidal maps

De Berg, Mark, Otfried Cheong, van Kreveld, Marc, Mark Overmars, "Computational Geometry: Algorithms and Applications", 3rd Ed., Springer, 2008.

Implementation of one or more algorithms studied along the course

The course is composed of frontal lessons, typically comprising practical case studies to better understand all the presented concepts and algorithms.
Together with the referral texts, additional material will be provided by means of PowerPoint slides and/or source code.

written