David Dumas

University of Illinois at Chicago

Spring 2012

The Voronoi diagram of a pseudorandom perturbation of the square lattice (selected cells shaded). |

Instructor | David 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) |

- CGAL - Computational Geometry Algorithms Library
- Dependencies of CGAL (full details)

apt-get install g++ cmake libcgal-demo

Homework | 30% |
---|---|

Projects | 30% |

Final project | 40% |

- 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

- Lecture 2 covers:
- Analysis of Algorithms notes by Steven Skiena --- lecture notes and audio

- MIT OpenCourseWare for SMA 5503 - Introduction to Algorithms - C. Leiserson and E. Demaine, including:
- 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

- Preparata, F. and Shamos, I. Computational Geometry: An Introduction, Springer-Verlag, 1990.
- 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

- Demo applet: Plane sweep for segment intersection by Wei Qian
- 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

- Art Gallery Theorems and Algorithms by Joseph O'Rourke
- 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):
- 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.

- Toth's work on the complexity of BSP for segments in the plane: