*Polygon:*

A polygon *P* is specified by its
vertices *(p1,...,pn)*
listed in clockwise order.

*Convex:**
*A simple polygon is convex if all its
internal angles are less than 180.

*Polygonal chain:*

A polygonal chain *Ci,j*
is a sequence of consecutive vertices *(pi,...,pj)* of P.

*Monotone chain:*

A polygonal chain is monotone with respect to a line *l* if the projections of *pk**, k=i,...,j,* on *l*
are ordered in exactly the same way as the vertices in *Ci,j* .

*Monotone polygon**:*

A polygon is monotone if there exists a line *l* such that the boundary of P can be partitioned into two polygonal
chains *Ci,j**, Cj,**i* which are monotone with respect to *l*.

*Properties(of a
polygon monotone in y direction): *

1. The Y-coordinates of points increase, then decrease steadily, as the
perimeter is traversed (from bottom to top).

2. Only the top point can have two neighbors with smaller
Y-coordinates, and similarly, only the bottom point can have two larger neighbors.

3. All horizontal lines intersect the boundary at most twice.

*Visible**:*

A point *x* in P is visible from a
point *y* in P, or equally, *y* can "see" *x*, if the open line segment joining *x* and *y* lies entirely inside P.

*Inward cusp**:*

A point is an inward cusp if its inside angle exceeds 180.

Dynamic programming is an
algorithmic paradigm that finds the best solution to a problem by combining
optimal solutions to subproblems.

Let's illustrate this with a simple
example of computing the Fibonacci numbers:

FIB(n)

**if** n=1or n=2 **then** return1 **else** return FIB(n-1)+ FIB(n-2)

This is inefficient, and we improve
the program by the following 2 dynamic programming forms:

FIB(n)

array(n)=0

**if** array(n) !=0

**then** return array(n)

**else**** **array(n)=
FIB(n-1)+FIB(n-2)

return array(n)

FIB(n)

array(1)=array(2)=1

**for** i **from**
3 **to** n **do** array(i)<---array(i-1)+array(i-2)

return array(n)

Both forms are similar in their use of
the array, but different in changing the control structure of the original
program.