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.

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.

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:

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:


1. Redundancy catching



if array(n) !=0

then return array(n)

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

       return array(n)


2. Aggregation



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.