Contents of this page 
Growing Set: avi mpg Final Set: avi mpg 
#  Date  Topic 

1  Friday, Sept. 10  List of likely course topics. 
2  Wednesday, Oct. 6  Description of course project. A list of potential projects is available from the professor. 
3  Monday, Nov. 29  Assessment form for project presentations. 
Homework Submission Policy:
#  Due Date  Assignment  Solution  Other Files 

1  September 22  Problem Set  Solutions  none 
2  October 6  Problem Set  Solutions  none 
3  October 20  Problem Set  Solutions  testImage.png,
testImage.bmp,
testImage.tiff,
Matlab image generation routine. Expected reach set for question #2. 
4  November 8  Problem Set  Solutions  none 
*  *  Midterm  Solutions  Mean 48.4, Standard Deviation 8, Median 50, Maximum 60.5, Minimum 35.5 
Course OverviewLevel set methods are a class of numerical algorithms for simulation of dynamic implicit surfaces and approximation of solutions to the HamiltonJacobi (HJ) partial differential equation (PDE).Dynamic implicit surfaces prove useful in such fields as:
The benefits of an implicit representation of surfaces include hassle free merging and separation of surfaces, easy computation of geometric properties like normals and curvature, and the fact that both curves in two dimensions and surfaces in three dimensions can be treated with the same theory and computational algorithms. The course will begin with an examination of numerical methods for computing dynamically evolving implicit surfaces. Students will experiment in Matlab with stateoftheart high order accuracy methods using a Toolbox of Level Set Methods developed by the instructor, and will therefore be able to progress rapidly to application specific details from the fields mentioned above. The second part of the class will turn to the HJ PDE, which arises in such fields as:
This component will examine generalizations of the level set methods mentioned above, as well as other classes of algorithms (including fast marching, ordered upwind, and sweeping) and some of the viscosity solution theory underlying this ubiquitous equation. Applications will be explored depending on students' interests. In addition to attending lectures, students will be expected to:

Intended Audience: Graduate students in
Prerequisites: None officially.
Instructor: Ian Mitchell
Lectures: 11  12:30, Mondays and Wednesdays, Forest Sciences Center (FSC) 1002
References:
Grades: Your final grade will be based on a combination of
Other References:
#  Date  Topic  Links  Required Readings  Optional Readings  

1  Sept 13  Introduction. Surface Representations.  Matlab's Introduction to initial value ODEs (available locally through Matlab's helpdesk command)  none.  Representations: Farin. Hoffmann. ODEs: Boyce & DiPrima chapter 8. Burden & Faires chapter 5. Heath chapter 9. 

2  Sept 15  Implicit Surface Functions. Constructive Solid Geometry. Matlab introduction.  Toolbox of Level Set Methods  OF chapter 1  T section 3.3  
3  Sept 20  Signed Distance Functions. Computer representation of continuous functions.  none  OF 2  OF 3.33.4, Heath 8.6, Burden & Faires 4.1, Strikwerda 1  
4  Sept 22  Motion by convective flow. Upwind spatial derivative approximation.  none  OF 3.13.2, T 2.1  T 3 (as needed), Heath 11.111.2, Burden & Faires 12.212.3  
5  Sept 27  Temporal derivative approximation. CFL timestep restriction. Multiple dimensional motion.  none  OF 3.2  none  
6  Sept 29  High order methods (TVD RK, ENO, WENO). Motion in the normal direction.  none  OF 3.33.5  T 2.7.2  
7  Oct 4  Motion in the Normal direction. Combinations of Motion. Reinitialization  none  OF 6.1, 6.2, 6.4, T 2.3.22.3.3  none  
8  Oct 6  Reinitialization Equation. Motion by Mean Curvature. Course Project Discussion.  none  OF 7.17.4, 4.14.3, T 2.2.1, 2.3.1, 2.4  S 2.32.4, 12.112.3  
Oct 11  Thanksgiving Holiday (no class)  
9  Oct 13  Constraints and Masking. Applications: Reach Sets (no inputs), Image Segmentation.  none  OF 12.1, T 2.2.3  S 12.4.3  
10  Oct 18  Optimal Control and the HamiltonJacobi Bellman equation.  none  none  Evans 10.3  
11  Oct 20  General first order HJ terms.  none  OF 5.1, 5.3, T 2.2.2, 2.5  OF 5.2  
12  Oct 25  Forcing terms. Differential Games.  none  none  "Differential Games and Representation Formulas for Solutions of HamiltonJacobiIsaacs Equations" by Evans & Souganidis, Indiana U. Math. J., v.33, n.5, pp.773797 (1984).  
13  Oct 27  Continuous Reach sets (with inputs)  Application of Level Set Methods to Control and Reachability Problems in Continuous and Hybrid Systems by Mitchell. Reach Set Lecture Slides.  T 2.6, section 2.1 of Mitchell  Mitchell 23  
14  Nov 1  Reach Sets: Projections & Hybrid Systems. Minimum time to reach.  Reach Set Lecture Slides.  none  S 20.120.3, Mitchell 46  
15  Nov 3  Static to TimeDependent Transformation.  "A Toolbox of HamiltonJacobi Solvers for Analysis of Nondeterministic Continuous and Hybrid Systems" by Mitchell & Templeton, submitted to HSCC 2005.  Mitchell & Templeton section 3.  "A Level Set Formulation for the solution of the Dirichlet Problem for HamiltonJacobi Equations" by Osher, SIAM J. Math. Anal. v.24, pp. 11451152 (1993).  
16  Nov 8  Fast Marching  "Efficient algorithms for globally optimal trajectories" by Tsitsiklas. "A fast marching level set method for monotonically advancing fronts" by Sethian.  OF 7.5  S 8  
Nov 10  Midterm exam  
17  Nov 15  Path Planning with Fast Marching Method.  Path Planning Slides. "Optimal Algorithm for Shape from Shading and Path Planning" by Kimmel & Sethian. "Continuous Path Planning with Multiple Constraints" by Mitchell & Sastry.  none.  none.  
18  Nov 17  Iterative and Sweeping Methods. Velocity Extension.  "Fast Sweeping Algorithms for a Class of HamiltonJacobi Equations" by Tsai et. al. "The Fast Construction of Extension Velocities in Level Set Methods" by Adalsteinsson & Sethian.  OF 8  S 11.211.4  
19  Nov 22  Conservation Laws. Particle Level Set Method.  "Animation and Rendering of Complex Water Surfaces" by Enright, Marschner and Fedkiw. "A Hybrid Particle Level Set Method for Improved Interface Capturing" by Enright et. al. PLS lecture slides.  OF 9  OF 1421  
20  Nov 24  Vector Level Sets. Stochastic Systems and the Kolmogorov Equation. Course Summary  "A Toolbox of HamiltonJacobi Solvers for Analysis of Nondeterministic Continuous and Hybrid Systems" by Mitchell & Templeton, submitted to HSCC 2005.  OF 10.110.3, Mitchell & Templeton section 4.  none.  
21  Nov 29  Project Presentations.  
22  Dec 1  Project Presentations.  
Dec 721  Exam period. Projects due at noon on Friday, December 17. 
Student  Topic  Title 

Eric Brochu  3D Visualization  Implicit Surface Ray Tracer 
Tyson Brochu  Faster Time Integration Algorithm  SemiLagrangian Time Integration 
Wan Chen  Image Segmentation Application  Active Contour Without Edges in Level Set Formulation 
Sarah Cormier  Algorithm to Reduce Computational Complexity  A Toolbox Implementation of the Local Level Set Method 
Kevin Loken  Algorithm to Reduce Numerical Dissipation  Particle Level Set Method 
Zhenguo Pan  New Type of Surface Motion  Level Set Method for Motion by Surface Diffusion 
Scott Olsen  Path Planning Application  Level Set Methods Approach to Optimal Path Planning 
Tiberiu Popa  Generation of Explicit Surface Representation in 3D  Survey of Triangulation Algorithms of Implicit Function Represented on Regular Grids 
Tim Rees  Financial Mathematics Application  A Level Set Approach to a Stochastic Differential Equation in Mathematical Finance 
Dana Sharon  Algorithm for Solving the Stationary HJB  Implementation of the Fast Marching Method 
Ian Stavness  Surface Reconstruction Application  Reconstruction of Surfaces from Unorganized Data Points 
David White  Additional Toolbox Features  Spatial and TimeDependent Boundary Conditions 
Alan Woo  Physically Based Modelling Application  LowSpeed Flame 
Yongning Zhu  Adaptive Mesh Refinement  Adaptively Refined Meshes for Level Set Functions 