Welcome to Computational Geometry homepage

Course prerequisites: Algorithms

Level: Advanced, BA, BSc, and higher degrees

Course Description:

Computational Geometry is the study of algorithms for solving geometric problems. The core of the field consists of a set of techniques for the design and analysis of such algorithms. It has deep connections to classical mathematics, theoretical computer science, and practical applications, that arise, e.g., in areas like statistics, computer vision, graphics, engineering, and more. The problems dealt with are typically posed as queries on sets of geometric objects, such as points, segments and polygons in the plane, or points, segments and polytopes in higher dimensions.

Tentative Scope of the Course In this course we will cover lines' and polygons' intersection problems, convex hulls, point location and range queries, proximity problems (Voronoi diagrams and Delaunay triangulations) and geometric optimization. We will study a variety of techniques, such as the sweepline paradigm, divide and conquer, and randomized algorithms. We will learn some geometric data structures. We will deal with applications of computational geometry to image matching, collision free robot's motion planning, and more.

Homework and grading (tentative): There will be up to 6 written homework assignments - for a total of 20 grade points. The exam will weigh 80 points.

The course's textbook is ``Computational Geometry: Algorithms and Applications'', by M. de Berg, M. van Kreveld,M. Overmars and O. Schwarzkopf, Springer-Verlag, 3rd edition 2008, also in paperback (there are copies in the library).

Other books that cover some of the topics:

• [CLR1] Cormen, Leiserson and Rivest, ``Introduction to Algorithms'', MIT Press, 1991.

• [CLR2] Cormen, Leiserson, Rivest and Stein ``Introduction to Algorithms, Third edition'', MIT Press, 2009.

• [Me] K. Mehlhorn, ``Data Structures and Algorithms 3:Multi-dimensional Searching and Computational geometry'', Springer-Verlag, 1984.

• [OR] J. O'Rourke, ``Computational Geometry in C'', Springer-Verlag, 1994.

• [PS] F. Preparata and M.I. Shamos, "Computational Geometry'', Springer-Verlag, 1988.

• [DO] S. Devadiss and J. O'Rourke, "Discrete and Computational Geometry'', Princeton University Press, 2011.

Schedule + book chapters from previous years can be found (soon) in Class material