Computational Geometry
Class Outline

COMPUTATIONAL GEOMETRY is the study of the representation and storage of geometric data and relationships, and the design, implementation and analysis of computational algorithms that operate on geometric data to answer questions of practical interest.

Some characteristic problems of computational geometry include:

• analysis: can we decompose a large geometric object into a collection of smaller objects of the same kind? Every soccer ball has 12 pentagons; why is it impossible to cover a ball using only six-sided figures?
• traversal: given a set of cities and an airline flight schedule, is a tour possible which visits all the cities exactly once?
• search: suppose we split each square of a checkboard into two triangles, and then place a penny in one triangle. Theoretically, we might need to check all 128 triangles to find the penny. Is it possible to search in such a way that no more than 8 triangles must be checked?
• projection: given a description of a 3D object, how do we make a 2D image of it? Our 2D image will usually depend on the point from which we view the object. What happens if our viewpoint is actually inside the object?
• sampling: what does it mean to pick a random point from a circle? What is different about the random pattern formed by throwing darts at a bull's-eye?
• interpolation: is it possible to find a formula for your signature? For your face?

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.