A polygon P is specified by its vertices (p1,...,pn) listed in clockwise order.
A simple polygon is convex if all its internal angles are less than 180.
A polygonal chain Ci,j is a sequence of consecutive vertices (pi,...,pj) of P.
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 .
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.
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.
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:
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:
if array(n) !=0
then return array(n)
else array(n)= FIB(n-1)+FIB(n-2)
for i from 3 to n do array(i)<---array(i-1)+array(i-2)
Both forms are similar in their use of the array, but different in changing the control structure of the original program.