This my phd thesis for the WDM optical network optimization, which employs Convex optimization techniques to solve the proposed integer problems. The computation complexity of my optimization framework is very low compared with other existing method and a performance bound is provided at the same time.
Input : A set S of planar points
Output : A Convex hull for S
Step 1: If S contains no more than five points, use exhaustive searching to find the Convex hull and return.
Step 2: Find a median line perpendicular to the X-axis which divides S into SL and SR SL lies to the left of SR .
Step 3: Recursively construct Convex hulls for SL and SR. Denote these Convex hulls by Hull(SL) and Hull(SR) respectively.
Step 4: Apply the merging procedure to merge Hull(SL) and Hull(SR) together to form a Convex hull.
Time complexity:
T(n) = 2T(n/2) + O(n)
= O(n log n)
A Convex Hull is the smallest Convex polygon that contains every point of the set S. A polygon P is Convex if and only if, for any two points A and B inside the polygon, the line segment AB is inside P.
One way to visualize a Convex hull is to put a "rubber band" around all the points, and let it wrap as tight as it can. The resultant polygon is a Convex hull.
