Introduction and Objective Introduction to data structures, algorithms, and analysis techniques for computational problems that involve geometry. Line segment intersection. Polygon triangulation and visibility problems. Linear programming. Range queries. Point location. Arrangements and duality. Voronoi diagrams and Delaunay triangulations. Convex hulls. Other selected topics. Programming assignments..
Textbook
M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf. Computational Geometry (2nd edition). Springer-Verlag, 2000. ISBN: 3-540-65620-0.
The book is accompanied by a website http://www.cs.uu.nl/geobook/which provides additional material such as pointers to software and research papers. For general background on algorithms, you can consult the following.
J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2005; ISBN 0-321- 29535-8.
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition MIT Press, 2001; ISBN 0-262-03293-7
Slides download here.
