Glossary

Convex polygon:A polygon is said

convexif the line that joins any two points of the polygon is entirely inside the polygon.

Convex polygon Non-convex polygon

Metric:A function D, usually called

distance, that respects the following properties when applied to x, y and z :

1. D(x, y) >= 0 (positiveness) 2. D(x, y) = 0 iff x = y (identity) 3. D(x, y) = D(y, x) (symmetry) 4. D(x, y) + D(y, z) >= D(x, z) (triangle inequality)

Monotone chain:A chain C (i.e. a sequence of edges) is said to be

monotonein a direction D if any line L orthogonal to D intersects C in exactly one point.

Monotone chain Non-monotone chain

A polygon P is monotone in some direction if an orthogonal line intersects P in no more than two points ; a convex polygon is monotone in

anydirection.

Simple polygon:A polygon with no self-intersecting edges. Since a polygon is defined by a sequence of vertices,

a priorinothing prevents any self-intersection of its edges.

Simple polygon

Non-simple polygon

Supporting line:Straight line L passing through a vertex of a polygon P, such that the interior of P lies entirely on one side of L. The supporting line is a generalization of the tangent.