Tuesday, May 13, 2003

Glossary of Terms

set P is
collection of points (where each point is presented in Cartesian coordinate) in the plane.

Convex Hull of P or C H (P)
is the smallest convex polygon that includes all points of P

Vertex
is a point; a location in Cartesian sense.
or, is intersection point of two sides.

Vertices of C H (P)
(plural) vertex
colection of points;
are points of P such that every point of P is either a vertex of C H (P) or lies inside C H (P)

Edges
are lines joining vertices.
each edge meets only two vertices (one at each of its ends) and
two edges must not intersect except at a vertex (which will then be a common endpoint of the two edges).

Faces
is collection of edges form the boundary of certain areas.
faces must not have holes in them or handles on them.
If two faces have common boundary points, then they must share a common edge (and only this), or a common vertex (and only this).

Tesselation
a situation where a shape, or shapes, can be fitted together to cover a surface so that there are no gaps

Triangulation of P
is partitioning a convex hull of P into triangles sucht that the vertex set of the partition is the set of points.

Delaunay Triangulation
is triangulation of a set P such that the minimum angle of its triangle is a maximum over all triangulations.

Voronoi diagram of P (n points)
is the nearest-neighbor map for a set of points.
is the dual of Delaunay triangulation.
is defined by Euler's relation; ie.
v - e + f = 2
to have O(n) edges and O(n) vertices

v = number of vertices
e = number of edges
f = number of regions,
of a planar subdivision.