MCS 481: Computational Geometry
University of Illinois at Chicago
The Voronoi diagram of a pseudorandom perturbation of the square lattice (selected cells shaded).
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++ cmake libcgal-demo
Your course grade will be determined on the following basis:
- Online resources for background in analysis of algorithms
- Computational Geometry in general
- Preparata, F. and Shamos, I. Computational Geometry: An Introduction, Springer-Verlag, 1990.
- O'Rourke, J. Computational Geometry in C, Cambridge University Press, 2001.
- 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.
- This general reference on data structures and algorithms covers some computational geometry in chapter 33
- Convex hulls
- 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 Triangulation and the Art Gallery Problem
- Orthogonal Range Searching
- Voronoi diagrams
- Arrangements of lines and discrepancy
- Binary Space Partition
- Toth's work on the complexity of BSP for segments in the plane:
- Wikipedia article IdTech1 with detailed discussion of the use of BSP in the computer game Doom.