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

January 8  Course Information and Tentative Outline.. 
Homework Submission Policy:
#  Topic  Assigned  Due Date  Assignment  Other Assignment Files & Links  Solution  Other Solution Files 

1  Implicit Surface Functions & Matlab Practice  January 15  January 22  Problem Set  Example Matlab function example.m, demonstrating coding style and useful plotting commands. If the formatting looks bogus, you might find it easier to get it from the ugrad server example.m.  TBA  
2  Dynamic Implicit Surfaces  January 29  March 2  Problem Set  none  TBA 
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. Although it was not covered this year, the second part of the class would have turned to the HJ PDE, which arises in such fields as:
This component would have examined 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. 
Intended Audience: Graduate students in
Prerequisites: None officially.
Computer Science Breadth: This course does not count toward the computer science graduate breadth requirement, because it concentrates on solving one particular class of PDEs, and hence does not cover the bigger picture of numerical differential equations. However, it is an introductory class in the sense that previous experience with PDEs is not necessary.
Instructor: Ian Mitchell
Lectures: 2:00  3:30, Mondays and Wednesdays, ICICS/CS 238
References:
Grades: Your final grade will be based on a combination of
Other References:
#  Date  Topic  Links  Required Readings  Optional Readings  

1  Jan 8  Introduction. Set & surface representations.  Introductory slides.  none.  Representations: Farin; Hoffmann. ODEs: Boyce & DiPrima 8; Heath 9. 

2  Jan 10  Set & surface tasks. Implicit surface function implementation of tasks, including constructive solid geometry and surface geometry  none.  OF 1  T section 3.3  
3  Jan 15  Signed Distance Functions. Toolbox Introduction.  Toolbox of Level Set Methods  OF 2  none.  
4  Jan 17  Computer representation of continuous functions: Finite difference and alternatives. Stability digression.  none  none  Heath 8.6, 9.3.1, 10.4; Strikwerda 1  
5  Jan 22  Types of differential equations: ODEs vs PDEs and IVPs vs BVPs vs IBVPs. Matlab function representation. Motion by convective flow.  none.  OF 3.1; T 3.13.3, 2.1  Heath 9, 10.110.2, 10.4, 11.111.3  
6  Jan 24  LaxRichtmayer equivalence and BarlesSouganidis extension. Upwind spatial derivative approximation. Temporal derivative approximation. CFL timestep restriction.  none  OF 3.2  Heath 11.2; G. Barles & P.E. Souganidis, "Convergence of Approximation Schemes for Fully Nonlinear Second Order Equations," Asymptotic Analysis volume 4, pp.271283 (1991). [not online]  
7  Jan 29  CFL timestep restriction. Multiple dimensional motion. OllivierGooch IAM talk.  none  OF 3.2  none  
8  Jan 31  High order methods (TVD RK, ENO, WENO).  none  OF 3.33.5  T 2.10.2  
9  Feb 5  Motion in the Normal direction. Combinations of Motion.  none  OF 6.1, 6.2, 6.4; T 2.3.22.3.3  none  
10  Feb 7  Reinitialization. Motion by Mean Curvature.  none  OF 7.17.4, 4.14.3, 6.3; T 2.2.1, 2.3.1, 2.4  S 2.32.4, 12.112.3; Adam M. Oberman, "A Convergent Monotone Difference Scheme for Motion of Level Sets by Mean Curvature," Numerische Mathematik, v.99, pp. 365379 (2004).  
11  Feb 12  General first order HJ terms. Other term: discounting, forcing.  none  OF 5.1, 5.3; T 2.2.2, 2.5, 2.8.2, 2.8.3  none  
12  Feb 14  Constraints and Masking. Applications: Reach Sets.  Reach Set Lecture Slides  T 2.2.3, 2.6  S 12.4.3; Adam M. Oberman, "Convergent Difference Schemes for Nonlinear Elliptic and Parabolic Equations: HamiltonJacobi Equations and Free Boundary Problems," SIAM J. Numerical Analysis, volume 44, number 2, pp. 879895 (2006); Claire J. Tomlin, Ian M. Mitchell, Alexandre M. Bayen & Meeko Oishi, "Computational Techniques for the Verification of Hybrid Systems," Proceedings of the IEEE, volume 91, number 7, pp. 9861001 (July 2003).  
13  Feb 14  Particle Level Set Method.  PLS lecture slides.  OF 5.2, 9; Doug Enright, Ronald Fedkiw, Joel Ferziger & Ian Mitchell, "A Hybrid Particle Level Set Method for Improved Interface Capturing," J. Computational Physics, volume 183, pp.83116 (2002).  OF 1421. Doug Enright, Steven Marschner & Ronald Fedkiw, "Animation and Rendering of Complex Water Surfaces," ACM Trans. Graphics (SIGGRAPH), volume 21, number 3, pp.736744 (2002); Frank Losasso, Ronald Fedkiw & Stanley Osher, "Spatially Adaptive Techniques for Level Set Methods and Incompressible Flow," Computers and Fluids, volume 35, pp. 9951010 (2006).  
Feb 1923  Midterm Break (no class)  
Feb 26  April 12  Lectures Cancelled. Project Meetings with Instructor.  
April 1630  Final Exam Period. Project Reports Due. 
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 