Polygon

A closed chain of n line segments (p_i, p_i+1) for 0 <= i <= n-1 and (p_n-1, p₀) , where n >= 3. The polygon P is represented by its vertices P = (p₀, p₁,..., p_n-1).

Simple Polygon

A polygon P with no two non-consecutive edges intersecting. There is a well-defined bounded interior and unbounded exterior for a simple polygon, where the interior is surrounded by edges. When referring to P, the convention is to include the interior of P.

Convex Polygon

A polygon P is convex if and only if for any pair of points x, y in P the line segment between x and y lies entirely in P.

Good Sub-Polygon

A good sub-polygon of a simple polygon P, denoted by GSP, is a sub-polygon whose boundary differs from that of P by at most one edge. This edge, if it exists, is called the cutting edge.

Anthropomorphic Polygon

A simple polygon containing precisely two ears and one mouth.

Convex Hull

The convex hull CH(P) of a polygon P is the smallest convex polygon that contains P.

Concave Vertex

A vertex p_i is concave if a left turn is made at p_i while going from p_i-1 to p_i+1 where the interior of the simple polygon P is to the right (ie. P is being traversed in clockwise order).

 

Convex Vertex

A vertex p_i is convex if a right turn is made at p_i while going from p_i-1 to p_i+1 where the interior of the simple polygon P is to the right (ie. P is being traversed in clockwise order).

 

Principal Vertex

A vertex p_i of simple polygon P is called a principal vertex if the diagonal (p_i-1, p_i+1) intersects the boundary of P only at p_i-1 and p_i+1.

Cutting Edge

The one edge of a good sub-polygon GSP that is not in simple polygon P (where GSP is a good sub-polygon of P).

 

Diagonal

A line segment lying entirely inside polygon P and joining two non-consecutive vertices p_i and p_j

 

Dual-Tree

Given a triangulated simple polygon, the dual-tree is the graph generated by plotting a vertex at each triangle and edges joining vertices in adjacent triangles (triangles which share a diagonal).

 

Ear

A principal vertex p_i of a simple polygon P is called an ear if the diagonal (p_i-1, p_i+1) that bridges p_i lies entirely in P. We say that two ears p_i and p_j are non-overlapping if the interior of triangle (p_i-1, p_i, p_i+1) does not intersect the interior of triangle (p_j-1, p_j, p_j+1).

 

Proper Ear

A proper ear of a good sub-polygon GSP is an ear of GSP which is not an end-point of the cutting edge of P.

Leaf

A vertex in a graph with only 1 edge incident to it.

 

Mouth

A principal vertex p_i of a simple polygon P is called a mouth if the diagonal (p_i-1, p_i+1) is an external diagonal, i.e., the interior of (p_i-1, p_i+1) lies in the exterior of P.

 

Triangulation

A triangulation of a simple polygon consists of n-3 non-intersecting diagonals or n-2 triangles where n is the number of vertices in the simple polygon.

 

Lines of Support

Given a convex polygons P, a line of support l is a line intersecting P and such that the interior of P lies to one side of l.

This concept is comparable to that of a tangent line.

Anti-Podal pairs

If two points p and q (belonging to P) admit parallel lines of support, then they form an anti-podal pair.

Two distinct parallel lines of support always determine at least one anti-podal pair. Depending on how the lines intersect the polygon, three cases arise:

1. Vertex-vertex anti-podal pair
2. Vertex-edge anti-podal pair
3. Edge-edge anti-podal pair

Case 1    Occurs when the lines of support intersect the polygon at two vertices only, as illustrated. The vertices shown as black dots form an anti-podal pair.

Case 2    Occurs when one line of support intersects the polygon at an edge while the other line of support is tangent at a vertex only. Note that the existence of such lines of support automatically implies the existence of two distinct vertex-vertex anti-podal pairs.

Case 3    Occurs only when the lines of support intersect the polygon at parallel edges. In this case, the lines of support also determine four distinct vertex-vertex anti-podal pairs.
 

One-Mouth Theorem

Except for convex polygons, every simple polygon has at least one mouth.

Two-Ears Theorem

Except for triangles every simple polygon has at least two non-overlapping ears.

Jordan Curve Theorem

A simple closed curve C in the plane divides the plane into exactly two domains, an inside and an outside.