Qoute of the day: ``Someone has to pay.''

1.  2D incremental Convex hull

1.1  Inductive assumption:

The Polygon is convex and has a set of remaining points partitioned by each edge.

Let P = {P₁,...,P_n} Ì R²

1.2  Algorithm

1. Extract 3 points from P and form a triangle, T. Pick C Î T

2. Draw a line segment for C to every point in P.

3. Partition P by which edge of T the line segment from C crosses.

4. While there exists point, P, above an edge, E, BuildTent(P,e,Polygon)

1. Remove all edges from the polygon visible by P.

2. Construct a larger polygon from the nonvisible edges in the Polygon + edges connecting to P.

3. associate points external to the polygon with the new edgeset of the polygon

1.3  Timing analysis

All the work occurs in the BuildTent routine.

In step 1, finding the visible edges will not be too costly because all the edges of all the polygons will form a planar graph. From euler's formula, if |v| = n and |E| = m then m £ 3n

The total cost of step 3 is the number of times that you must check whether a line segment between P_i and C .

To analyze step 3, run the algorithm backwards.

• At T(n), Poly = convexhull( P₁,...,P_n )

• T(n-1) = T(n) - the comparisons necessary to insert P_n into the polygon.

• The cost to extract a node p on the hull = # of intersections on left and right edges of P

• At a particular point in time. |P| = K

• å_{p Î P}ExtractCost(P) = 2*#intersections £ 2n

• E(ExtractCost) £ 2n/k

• E(#intersections) £ å_{k = n}¹2n/k = 2n*å_{k = 1}ⁿ1/k = O(n*log₂(n)

2.  Linear Programming

After rotation, the problem is finding the point (x,y) which minimizes the y value.

Constraints can all be written in one of the forms:

1. H⁺ = {i:y ³ a_ix+b_i} = constraints on the minimum value of y

2. H^- = {i:y £ a_ix+b_i} = constraints on the maximum value of y

3. H⁰ = {i:a_ix £ b_i} = vertical constraints