(600.459)

This course will provide an introduction to computational geometry. It will cover a number of topics in two- and three-dimensions, including polygon triangulations and partitions, convex hulls, Delaunay and Voronoi diagrams, arrangements, and spatial querries. Students are encouraged to complete the assigned reading before class, and will be required to implement a number of the discussed techniques. (Audits will not be allowed.)

- Meeting Time: Monday and Wedensday 1:30-2:45
- Meeting Place: Maryland 214
- TA: Fabian Prada
- Textbook (required): Computational Geometry in C,
*O'Rourke*. - Textbook (optional): Computational Geometry,
*de Berg et al.*

- Polygon Triangulation:
**02/21/16** - Convex Hull (2D) Calculation:
**03/13/16** - Convex Hull (3D) and Delaunay Triangulation (2D) Calculation:
**05/05/16**

Date | Reading | Notes |
---|---|---|

01/27/16 | Introduction | |

02/01/16 | Chapter 1 | Triangulation |

02/03/16 | Triangulation | |

02/08/16 | Chapter 2 | Polygon Partitioning |

02/10/16 | Polygon Partitioning | |

02/17/16 | Chapter 3 | Convex Hulls (2D) |

02/22/16 | Convex Hulls (2D) | |

02/24/16 | Chapter 4 | Convex Hulls (3D) |

02/29/16 | Convex Hulls (3D) | |

03/02/16 | Convex Hulls (3D) | |

03/07/16 | Chapter 5 | Voronoi Diagrams and Delaunay Triangulations |

03/09/16 | Voronoi Diagrams and Delaunay Triangulations | |

03/14/16 | Spring Break | |

03/16/16 | ||

03/21/16 | Chapter 6 | Arrangements |

03/23/16 | Arrangements | |

03/28/16 | Chapter 7 | Search and Intersection |

03/30/16 | Class Cancelled | |

04/04/16 | ||

04/06/16 | ||

04/11/16 | Chapter 7 | Search and Intersection |

04/13/16 | Search and Intersection | |

04/18/16 | Chapter 8 | Motion Planning |

04/20/16 | Motion Planning | |

04/25/16 | Motion Planning | |

04/27/16 | Chapter 7 | Search and Intersection |

- QHull
- ANN: A Library for Approximate Nearest Neighbor Searching
- Triangle
- TetGen
- Computational Geometry Algorithms Library

- Convex Hulls of Finite Points in Two and Three Dimensions, Preparata and Hong (1977)
- Medial Axis Transformation of a Planar Shape, Lee (1982)
- A New Linear Algorithm for Intersecting Convex Polygons, O'Rourke, Chien, Olson, and Naddor (1982)
- Fast Detection of Polyhedral Intersection, Dobkin and Kirpkpatrick (1983)
- Intersection of Convex Objects in Two and Three Dimensions, Chazelle (1987)
- Constrained Delaunay Triangulations, Chew (1987)
- Power Diagrams: Properties, Algorithms and Applications
- Art Gallery Theorems and Algorithms, O'Rourke (1987)
- Provably Good Mesh Generation, Bern
*et al*. (1990) - Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure, Aurenhammer (1991)
- Triangulating a Nonconvex Polytope, Chazelle
*et al*. (1992) - Quality Mesh Generation in Three Dimensions, Mitchell
*et al*. (1992) - Three-Dimensional Alpha Shapes, Edelsbrunner
*et al*. (1994) - Algorithms for Ham-Sandwich Cuts, Lo
*et al*. (1994) - Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions, Chan (1996)
- Delaunay Refinement Mesh Generation, Shewchuk (1997)
- Tetrahedral Mesh Generation by Delaunay Refinement, Shewchuk (1998)
- A Minimalist's Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm, Chan (2003)