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:
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.