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,
Basic knowledge of the design and analysis of algorithms and data structures:
big-Oh notations, sorting, binary search, balanced
search trees...etc. Some basic knowledge in probability theory.
Introduction to the course
Line segment intersection & thematic map overlay.
Orthogonal range searching
Geometric data structures
Homework assignments: homework1, homework2,
and a project:
You are asked to write a project proposal before starting any project!!!
Programming project: implement one of the algorithms presented in
Survey project: write a survey on a computational geometry related