https://studiegids.vu.nl/en/courses/2024-2025/XM_0168Geometry exists almost everywhere and there are computational problems in many different places in which geometry plays a crucial role. Designing efficient route-finding algorithms in robotics systems, helping scientists to build efficient tools for analyzing trajectory data, designing fast solutions for traffic management, designing efficient search procedures in geographical domains, and many more applications, require knowledge of algorithmic geometry. In order to deal with and solve such geometric problems, exclusively geometric-based algorithms and tools are needed. To this end, computational geometry emerged from the field of algorithms design and analysis in the late 1970s and its goal is to design efficient algorithms and data structures for problems involving and dealing with geometry. Since its birth in the late 1970s, it has then grown into a recognized discipline with its own journals, conferences, and a large community of active researchers. As such, we note that this course is distinguished from a non-geometry algorithms course as it has exclusively geometric-based tools and techniques, which do not appear in a non-geometry algorithms course. Thus, the course can be regarded as a complementary addition to graduate programs. There are currently many CS departments across the world that teach the course to their MSc and PhD students. The goal of the course is to study the most important notions, tools, and techniques needed to design geometric algorithms and data structures. After taking this course, you: i) have basic knowledge of geometric algorithms and geometric data structures (Knowledge and understanding) ii) have basic knowledge of tools and geometric-based algorithms for solving some geometric problems (Knowledge and understanding) iii) are able to analyze the performance of (some) geometric algorithms, with regard to their time and space requirements. (Applying knowledge and understanding) (Making judgements)The goal of the course is to study the most important notions, tools, and techniques needed to design geometric algorithms and data structures. A list of standard topics in the course includes, but is not limited to, convex hulls, sweep-line algorithms, kd-trees, range searching, triangulation and the Art Gallery problem, Voronoi diagrams and the Post Office problem, arrangement and duality, and several basic geometric data structures. In this course, we will discuss some or all of these topics, depending on the availability of time and the students' interests.There will be two lectures and one exercise sessions per week. Attendance is not mandatory, but it is strongly recommended.There will be only one final exam at the end of the course covering all the materials.We will use the following well-known textbook as the main reference in the course. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008.The students are assumed to have a good knowledge in undergraduate courses in design and analysis of algorithms and data structures. In particular, they should be familiar with asymptotic notations and how to analyze the running times of algorithms and simple algorithmic techniques like sorting, binary search, and balanced search trees. No prior knowledge in geometry is required.We will use Canvas for our communications, posting announcements, publishing materials of the course (e.g., course slides, weekly exercises, and any other additional related materials).