Computational Discrete Geometry

**
**
Spring 2007

Student Lectures

March 1 | Tim Lee | Geometric hashing |

March 8 | Chris O'Neill | Polygon triangulations |

March 15 | Arash Farahmand | Computational convexity |

March 22 | Anastasia Chavez | Delaunay triangulations |

April 5 | Brendan Colloran | Voronoi diagrams |

April 19 | Philipp Richter | Quadtrees |

April 19 | Yelena Gartsman | Efficient distance computation between non-convex objects |

April 26 | Ido Heskia | Factoring polynomials with rational coefficients |

April 26 | Connie Phong | Surface Simplification and 3D Geometry Compression |

**Suggested Topics**

- Sections 3.2-3.3 in De Berg-van Kreveld-Overmars-Schwarzkopf
- Sections 5.2-5.4 in De Berg-van Kreveld-Overmars-Schwarzkopf
- Sections 6.1-6.3 in De Berg-van Kreveld-Overmars-Schwarzkopf
- Sections 9.1-9.4 in De Berg-van Kreveld-Overmars-Schwarzkopf
- Sections 12.1-12.3 in De Berg-van Kreveld-Overmars-Schwarzkopf
- Sections 14.1-14.4 in De Berg-van Kreveld-Overmars-Schwarzkopf
- Sections 15.1-15.3 in De Berg-van Kreveld-Overmars-Schwarzkopf
- Sections 16.1-16.3 in De Berg-van Kreveld-Overmars-Schwarzkopf
- Godfried T. Toussaint and Jim A. McAlear, A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets, Pattern Recognition Letters, vol. 1, October 1982, pp. 21-24, and Godfried T. Toussaint and Binay K. Bhattacharya, "Optimal algorithms for computing the minimum distance between two finite planar sets," Proc. Fifth International Congress of Cybernetics and Systems, August 1981.
- Michael E. Houle and Godfried T. Toussaint, Computing the width of a set, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, No. 5, September, 1988, pp. 761-765.
- H. Wolfson and I. Rigoutsos, Geometric Hashing: An Overview, IEEE Computational Science and Engineering, 4, pp. 10-21, 1997.
- J. S. Quinlan, Efficient distance computation between non-convex objects, Proc. International Conf. on Robotics and Automation, pp. 3324-3329, 1994.
- Nataraj Akkiraju, Herbert Edelsbrunner, Michael Facello, Ping Fu, Ernst P. Muecke, Carlos Varela, Alpha Shapes: Definition and Software.
- A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515-534.
- Dan Halperin, Arrangements, in: Handbook of Discrete and Computational Geometry (J. E. Goodman and J. O'Rourke, eds.), 2nd edition, Chapman & Hall, 2004.
- Marshall Bern, Triangulations and mesh generation, in: Handbook of Discrete and Computational Geometry (J. E. Goodman and J. O'Rourke, eds.), 2nd edition, Chapman & Hall, 2004.
- Peter Gritzmann & Victor Klee, Computational convexity, in: Handbook of Discrete and Computational Geometry (J. E. Goodman and J. O'Rourke, eds.), 2nd edition, Chapman & Hall, 2004.
- David Dobkin & Seth Teller, Computer graphics, in: Handbook of Discrete and Computational Geometry (J. E. Goodman and J. O'Rourke, eds.), 2nd edition, Chapman & Hall, 2004.
- Jarek Rossignac, Surface simplification and 3d geometry compression, in: Handbook of Discrete and Computational Geometry (J. E. Goodman and J. O'Rourke, eds.), 2nd edition, Chapman & Hall, 2004.