MCS 481: Computational Geometry

Emily Dumas

University of Illinois at Chicago
Spring 2011

General information

Instructor	Emily Dumas (ddumas@math.uic.edu)
Office hours	Mondays 4-5 and Wednesdays 11-12 in SEO 503
CRN	31103 (undergraduate), 31104 (graduate)
Lectures	MWF 2:00 - 2:50pm in Lincoln Hall 321
Text	de Berg, Cheong, van Kreveld, and Overmars.  Computational Geometry: Algorithms and Applications, 3ed. Springer-Verlag, 2008. ISBN-13: 978-3540779735   (compare prices and availability at several booksellers)

Course Materials

• Course syllabus
• Final Project Information

Assignments

Software

• CGAL - Computational Geometry Algorithms Library
• Dependencies of CGAL (full details)
  • A supported C++ compiler, such as gcc/g++
  • cmake build system
  • boost general-purpose C++ library

CGAL and its dependencies are available as binary packages for some operating systems, including several versions of GNU/Linux, and this is often the easiest way to install these programs. For example, on recent versions of Debian GNU/Linux, all of the necessary packages can be installed with the command:

apt-get install g++ libcgal5 libcgal-demo

Grading

Your course grade will be determined on the following basis:

Homework	30%
Projects	30%
Final project	40%

Resources

• Computational Geometry in general
  • Preparata, F. and Shamos, I.  Computational Geometry: An Introduction, Springer-Verlag, 1990.
    ISBN-13: 978-3540961314
  • O'Rourke, J.  Computational Geometry in C, Cambridge University Press, 2001.
    ISBN-13: 978-0521649766
    • This is a good reference for details of implementation in a low-level language like C
  • Cormen, T., Leiserson, C., Rivest, R., and Stein, C.  Introduction to Algorithms, 2nd ed., MIT Press, 2001.
    ISBN-13: 978-0262032933
    • This general reference on data structures and algorithms covers some computational geometry in chapter 33
• Convex hulls
  • Notes on 2D convex hulls by Jeff Erickson.
  • Demonstration of the quick-hull algorithm
  • qhull, a C implementation of quick-hull in any number of dimensions
• Segment Intersection and Map Overlay
  • Demo applet: Plane sweep for segment intersection by Wei Qian
    • Select "Data Set 1" then use the horizontal scrollbar to visualize the sweep.
  • The DCEL representation of a planar subdivision is discussed in Section 1.2.3 of Preparata and Shamos (see reference above)
  • An important special case of the overlay of planar subdivision is the polygon boolean operation problem, i.e. computing the intersection, difference, or union of two polygons. The intersection case is also called polygon clipping.
    • Polygon clipping applet by Christopher Andrews
    • Comparison of various implementations of polygon boolean operations
• Polygon Triangulation and the Art Gallery Problem
  • Art gallery applet and discussion by Thierry Dagnino
  • References for the triangulation of monotone polygons using mountains:
    • Lecture notes by Sariel Har-Peled. Discussed: polygon -> monotone -> mountains -> triangles
    • Lecture notes by Jeff Erickson. Discussed: mountains -> triangles, monotone -> triangles
• Voronoi diagrams
  • Voronoi Diagrams and a Day at the Beach by David Austin (AMS feature column, Aug 2006)
  • Java applets demonstrating Fortune's algorithm (by David Austin):
    • Interactive Voronoi diagram
    • The beach line
    • Break points sweep out Voronoi edges
  • A visual implementation of Fortune's Voronoi algorithm by Allan Odgaard & Benny Kjaer Nielsen
  • Javascript implementation of Fortune's algorithm with extensive visualization options

Up: Home page of Emily Dumas