## Definitions

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:

1. Redundancy catching

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)

2. Aggregation

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.