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 sixsided 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'seye?

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

The fundamental objects: points, lines and curves, planes and surfaces, spaces

The fundamental relations: inclusion, containment, perpendicularity, intersection

The fundamental measures: distance, angle, length, area, volume, projected length

The fundamental operations: interior, exterior, intersection, normal vector

Other basic ideas: convexity, change of coordinate system, equal spacing

The circle and the disk; polar coordinates

The sphere and the ball; spherical coordinates

The Triangle; area, orientation, angles, aspect ratio;
containment, barycentric coordinates; distance from a point to a triangle

Polygons; partitioning a polygon

The Simplex

Polyhedrons: vertices, edges, faces; orientation

The description and approximation of 2D curves:
y = f(x); polynomial interpolation; piecewise interpolations; least squares approximations;
f(x,y) = 0;
finite element approximation;

Sampling and Random Selection; uniform and nonuniform densities;
rejection methods; transformation methods; sampling inside or on a sphere

The Convex Hull

Triangulation; Generating a triangulation; measures of uniformity;
Delaunay triangulations; searching a (Delaunay) triangulation;

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.

Voronoi Diagrams in the plane; Voronoi diagrams restricted to a region;
Voronoi diagrams on a sphere; Voronoi diagrams in higher dimensions

The Nearest Neighbor Problem

Storing, retrieving, displaying geometric information

Quadrature; derivatives

Software: OpenGL, Triangle, DISTMESH

Surface refinement, simplification, modification
You can return to the
HTML web page.
Last revised on 25 September 2008.