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
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
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
Software: OpenGL, Triangle, DISTMESH
Surface refinement, simplification, modification
You can return to the
HTML web page.
Last revised on 25 September 2008.