Geometric Algorithms

Computer graphics, robot motion planning, computer games, simulations, geographic information systems, and CAD/CAM systems all make use of geometric algorithms to perform various tasks. The course on geometric algorithms takes a fundamental viewpoint and discusses the design and analysis of geometric algorithms. We will study various algorithmic techniques and geometric concepts that are useful to solve geometric problems efficiently. These include plane sweep, randomized incremental construction, and multi-level data structures; geometric concepts include Voronoi diagrams and Delaunay triangulations, arrangements, and duality. We will apply these techniques to solve a variety of problems: convex-hull computation, line-segment intersection, polygon triangulation, low-dimensional linear programming, range searching, and point location are some examples. Each problem we study is motivated by a practical problem from one of the application areas.

Review A+BE PhD candidate
'This course is from the area of computer science which is somehow related to the scope of Geographic Information Science PhD candidates. It’s a Msc-course, not specifically targeted at PhDs, but it does help to fill the gap for discipline related courses for our field (Geographic Information Science). Both the contents and the teacher, prof. Van Kreveld, are very good. It did cost a lot of time though: A lot of homework assignments and an exam. The course is worth 7,5 ECTS, which is converted to 5 GS credits (the maximum allowed).'   

Course at a Glance

University
University of Utrecht

Level
MSc

Duration
10 weeks

Courseload
Two lectures of in total 4 hours per week. Plus assignments and exam. 

Description
Link to course description