Computational Geometry
Class Outline

COMPUTATIONAL GEOMETRY is the study of the representation of goemetric data and relationships, and the development and analysis of algorithms to store and manipulate that data.

Computational Geometry has applications thoughout computational science, most naturally in areas which have a strong geometric component. However, even in abstract computations involving multidimensional data, insights and algorithms originally developed for "physical" (2D or 3D) problems can be extended to the high dimensional case.

Computational Geometry Schedule

  1. The fundamental objects: points, lines and curves, planes and surfaces, spaces
  2. The fundamental relations: inclusion, containment, perpendicularity, intersection
  3. The fundamental measures: distance, angle, length, area, volume, projected length
  4. The fundamental operations: interior, exterior, intersection, normal vector
  5. Other basic ideas: convexity, change of coordinate system, equal spacing
  6. The circle and the disk; polar coordinates
  7. The sphere and the ball; spherical coordinates
  8. The Triangle; area, orientation, angles, aspect ratio; containment, barycentric coordinates; distance from a point to a triangle
  9. Polygons; partitioning a polygon
  10. The Simplex
  11. Polyhedrons: vertices, edges, faces; orientation
  12. The description and approximation of 2D curves: y = f(x); polynomial interpolation; piecewise interpolations; least squares approximations; f(x,y) = 0; finite element approximation;
  13. Sampling and Random Selection; uniform and nonuniform densities; rejection methods; transformation methods; sampling inside or on a sphere
  14. The Convex Hull
  15. Triangulation; Generating a triangulation; measures of uniformity; Delaunay triangulations; searching a (Delaunay) triangulation;
  16. Adaptive meshing; binary trees for adaptive interval meshing; quadtrees for 2D; octrees for 3D meshing. Locating a point in a mesh defined by a tree.
  17. Voronoi Diagrams in the plane; Voronoi diagrams restricted to a region; Voronoi diagrams on a sphere; Voronoi diagrams in higher dimensions
  18. The Nearest Neighbor Problem
  19. Storing, retrieving, displaying geometric information
  20. Quadrature; derivatives
  21. Software: OpenGL, Triangle, DISTMESH
  22. Surface refinement, simplification, modification

You can return to the HTML web page.

Last revised on 25 September 2008.