David Dumas

University of Illinois at Chicago

Spring 2011

Overlapping polygons and a triangulation of the induced planar decomposition. |

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

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

apt-get install g++ libcgal5 libcgal-demo

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

Projects | 30% |

Final project | 40% |

- 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 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):
- A visual implementation of Fortune's Voronoi algorithm by Allan Odgaard & Benny Kjaer Nielsen
- Javascript implementation of Fortune's algorithm with extensive visualization options