Assignments, Due Dec. 6

Final Project Assignment (Due Dec. 13)

Write a 5 + page document about an application of Computational Geometry. You can choose the application either based on your own research project or research interests, or based on what you can find on-line Googling. Examples of applications include: image processing, data mining, robotics, statistics, network design and optimization, sensor networks, scientific computing, engineering simulation, graph theory etc. You should

Course Schedule (tentative)

Last revised on: 09/03/04 3:19 PM

Reading assignments are given according to the main text book.

 
Lec#
Date
Topic and/or Event Reading Notes
1
9/13
Class Organization
      Class Webpage
      Introduction and Readings
Geometry: 1, 2, and higher dimensions
Convex Hulls
Voronoi Diagrams and Delaunay Triangulations
Chapters 1, Chapter 7 and Chapter 9
Note by Lori Venegas
 
2
9/20
Properties of Delaunay Triangulations Chapters 1, 7, 9
Note by Kebin Wang
 
3
9/27
Class is rescheduled to 10/08/2004, same time at MCS 137    
3
10/4
Delaunay Algorithms (local and randomized)
      and Backward Analysis
Chapters 4, 7,9
Note by Chizube Anazodo

 

4
10/8
Rescheduled class at MCS 137 (Friday) More on Backward Analysis
      Randomized Linear Programming
Chapters 4, 7,9
Note by Vladimir Rydzevskiy

 

5
10/11
No Class: Holiday  

 

6
10/18
Class to be rescheduled possibly to Oct 29
Ruppert Algorithms: Delaunay Refinement and Mesh Generation
Sphere Packing and Delaunay Meshes
Handout  
7
10/25
Mesh Generation: Ruppert's Delaunay Refinement Algorithms
Weighted Delaunay Triangulation in 3D: Sliver Removal
Handout 1: Ruppert's Original Paper
Handout 2: A survey paper by Teng and Wong
Note By Niky Riga
 
8
11/1
Sphere Packing and Delaunay Meshes handout
Handout: Parallel Delaunay by Spielman-Teng-Ungor et al by Maosen Fang
 
6 (make up)
10/18
Rescheduled class at MCS 137
Parallel Delaunay Meshing
Handout: same as the previous lecture
Note by yevgen Tsykynovsky
 
9
11/8
Geometric Divide and Conquer and Nearest Neighbor Problems Miller-Teng-Thurston-Vavasis
Notes by Feifei Li
 
10
11/15
Sphere Separators and Geometric Partitioning handout: same as the last lecture
Notes by Dihan Cheng
 
11
11/22
Conformal Maps handout: same as the last lecture
Notes by Jared Wickman
 
12
11/29
Geometric Sampling and Center Points Handout
Clarkson's page
Notes by Zhuangli Liang
 
13
12/6
Iterative Radon Method for Centerpoints Handout
Notes by Xin Qi
 
14
12/13
Spectral Geometric and Spielman-Teng Eigenvalue Bounds
Curve Restruction and Surface Restruction and Other Geometric Algorithms
handout