CG/S2010
From ResearchWiki
Computational Geometry (Spring 2010)
MEB 2325: TH 3:40-5
Textbook: Computational Geometry: Algorithms and Applications
Mailing list: cs6160@list.eng.utah.edu
Homework style file: assign.cls
Contents |
Schedule
| Date | Topic | Date | Topic |
|---|---|---|---|
| Jan 12 | Convex Hulls I | Jan 14 | Convex Hulls II |
| Jan 19 | No class: Suresh @ SODA | Jan 21 | No class: Suresh @ SODA |
| Jan 26 | Voronoi Diagrams | Jan 28 | Delaunay Triangulations I, Homework 1 and LaTeX (due Feb 4, 2010) |
| Feb 2 | Delaunay Triangulations II | Feb 4 | Duality and Arrangements |
| Feb 9 | Segment Intersections (Project proposals due today) | Feb 11 | Point Location, and trapezoidal decompositions. Homework 2 and LaTeX (due Feb 18, 2010) |
| Feb 16 | 1D and 2D range searching (chapter 5) (and some notes) | Feb 18 | k-D trees (chapter 5), and the start of Windowed Search (chapter 10) (more notes) |
| Feb 23 | Windowed Search (continued): interval trees and segment trees | Feb 25 | Quad Trees |
| Mar 2 | Path Planning I: Minkowski Sums | Mar 4 | Path Planning II: Visibility Graphs |
| Mar 9 | Linear Programming I: Polytopes | Mar 11 | Linear Programming II: Algorithms |
| Mar 16 | Dimensionality Reduction | Mar 18 | The Johnson-Lindenstrauss Lemma |
| Mar 30 | Core Sets I: Epsilon-kernels | Apr 1 | Core Sets II: Variations |
| Apr 6 | VC Dimension I | Apr 8 | VC Dimension II |
| Apr 13 | no class.. | Apr 15 | Art Gallery Theorems |
| Apr 20 | Combinatorial Geometry | Apr 22 | Floor function considered dangerous... |
| Apr 27 | Computational Origami |
Project Proposals
- Christopher Bireley
- Jeremiah Darais
- Shusen Liu
- Dan Maljovec
- Toren Monson
- Bigyan Mukherjee
- Gene Peterson
- Hao Wang
Project Presentations
May 4, 2010
May 6, 2010
Project Examples
Below are initial 2-page summaries and final projects from last spring. This list is to help you get an idea of the kinds of things that are within scope. It's not exhaustive by any means.
Spring 2009
- Dimensionality reduction with spherical constraints: initial, final
- A survey of the Johnson-Lindenstrauss Lemma: initial, final
- Ray Tracing Acceleration Structures: Constrained Tetrahedralizations vs. KD Trees: initial, final
- 3D-Modeling Using Shape from Silhouette Algorithms: initial, final
- Survey of Surface/Curve Reconstruction Techniques: initial, final
- Isotropic PCA for Document Clustering: initial, final
- The Fold and Cut Problem: initial, final
- Implementation of low-dimensional approximate near neighbour algorithms: initial, final
- Understanding metric properties of Bregman divergences: initial, final
- Analysis and Approximation of the Weiszfeld Algorithm: initial, final
