Description
Computational Geometry has emerged in late 1970s motivated by the need
of geometric algorithms in new arising application domains such as computer
graphics, robotics, geographical information systems (GIS)... This relatively
new discipline produced a number of new algorithmic techniques improving
early solutions to some geometric problems.
In this course we present some of these geometric problems and their
algorithmic solutions. Since the course is application oriented we are
not necessarily looking at optimal algorithms but the ones that are easiest
to understand and implement. However, for each chapter, there will be some
short discussions about the status of the research: faster algorithms,
open problems...etc.
Prerequisites
Basic knowledge of the design and analysis of algorithms and data structures:
bigOh notations, sorting, binary search, balanced
search trees...etc. Some basic knowledge in probability theory.
Contents

Introduction to the course

Line segment intersection & thematic map overlay.

Polygon triangulation

Orthogonal range searching

Point location

Voronoi diagrams

Delaunay triangulation

Geometric data structures
Examination
Homework assignments: homework1, homework2,
homework3
and a project:

Programming project: implement one of the algorithms presented in
class.

Survey project: write a survey on a computational geometry related
topic.
You are asked to write a project proposal before starting any project!!!
WWW links
http://www.cs.ruu.nl/geobook
http://www.cs.ubc.ca/spider/snoeyink
Questionnaire