Geometric Algorithms

Professor: Evanthia Papadopoulou
Assistant: Maksym Zavershynskyi

Tipo di corso: Lecture
Valore in crediti ECTS: 6


Academic year 2012/2013 - Spring semester


Pre-requisites: Algorithms and Complexity


Objectives
This course is an introduction to computational geometry and its applications with a focus on algorithms and data structures. The course will cover various techniques needed in designing and analyzing efficient algorithms and data structures for computational problems in discrete geometry, such as convex hulls, triangulations, geometric intersections, Voronoi diagrams and Delaunay triangulations, arrangements of lines and hyperplanes, range searching. Computational geometry is well related to a variety of application domains in which geometric algorithms play a fundamental role, such as computer-aided design (CAD), pattern recognition, image processing, computer graphics, computational science, information retrieval, geographic information systems (GIS), robotics, and many others. The course will cover general algorithmic techniques, such as plane sweep, divide and conquer, incremental construction, randomisation, and approximation, through their application to basic geometric problems.


Contents

  • Convex hulls
  • Linear programming: half-plane intersection, randomized LP, applications of low-dimensional LP.
  • Intersections and triangulation: plane-sweep line segment intersection, triangulation of monotone subdivisions, plane-sweep triangulation of simple polygons.
  • Planar point location, trapezoidal decompositions.
  • Voronoi diagrams, plane sweep construction, generalizations
  • Geometric data structures: kd-trees, range trees, range searching, segment trees, nearest neighbor searching.
  • Delaunay triangulations: point set triangulations, randomized incremental construction and analysis.
  • Arrangements and duality
  • Geometric approximation: well-separated pair decompositions and geometric spanners


Teaching mode
Lectures, exercise sessions, homework and/or project assignment.


References
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, “Computational Geometry, Algorithms and Applications”, Springer-Verlag, 3rd ed. , 2008
J. O’ Rourke, “Computational Geometry in C”, 2nd ed., Cambridge University Press
David Mount, Computational Geometry lecture notes http://www.cs.umd.edu/class/spring2007/cmsc754/Lects/754lects.pdf