MCS 481: Computational Geometry

Emily Dumas

University of Illinois at Chicago
Spring 2012

General information

Instructor	Emily Dumas (ddumas@math.uic.edu)
Office hours	Wed and Fri 11am-12pm in SEO 503
CRN	31103 (undergraduate), 31104 (graduate)
Lectures	MWF 2:00 - 2:50pm in Taft Hall 219
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

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++ cmake libcgal-demo

Grading

Your course grade will be determined on the following basis:

Homework	30%
Projects	30%
Final project	40%

Resources

• Online resources for background in analysis of algorithms
  • MIT OpenCourseWare for SMA 5503 - Introduction to Algorithms - C. Leiserson and E. Demaine, including:
    • Lecture 2 covers: O, Ω,Θ notation and the Master Theorem on recurrences
  • Analysis of Algorithms notes by Steven Skiena --- lecture notes and audio
• 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 Theorems and Algorithms by Joseph O'Rourke
    • Includes discussion of NP-hardness of the minimal art gallery problem (chapter 9)
  • 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
• Orthogonal Range Searching
  • KD-tree demo applet by H. Akcan
• 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
• Arrangements of lines and discrepancy
  • Proof of the zone theorem using Davenport-Schinzel sequences, notes by Samir Khuller.
  • Davenport-Schinzel sequences and their geometric applications by Sharir and Agarwal. (Link goes to book information with links to several online retailers.)
• Binary Space Partition
  • Toth's work on the complexity of BSP for segments in the plane:
    • A note on binary plane partitions - Worst case BSP size Ω(n log(n) / log(log(n))), 2001
    • Binary plane partitions for disjoint line segments - BSP of size O(n log(n) / log(log(n))) exists (2009)
  • Wikipedia article IdTech1 with detailed discussion of the use of BSP in the computer game Doom.

Up: Home page of Emily Dumas