6.838J/4.214J - Interactive Geometric Data Structures and Computation

Meeting 5 (2/18/98)  Planar Convex Hull
 
Haiyang Liu      Wei Cai
 
 
Definitions of Planar Convex Hull:  
 		  
 
 
  • Mathematical Definition
A subset S of the plane is called convex if and only if for any pair of points (p,q) belonging to S the line segment pq is completely contained in S.   
 
  • More Operatable Definition
  
 
If all points belonging to S other than p and q lie to the right of or on the directed line through p to q, then pq is an edge of convex hull of S. 

All edges consist of a complete convex hull. 
 

  
 
  
 
 
 
 
 
 
Fundamental Data Structures for Planar Convex Hull Computing  
 
Point : 

1D Array with dimension of 2 (every element pointing to a coordinate). 
 

   
 
Edge (w/o direction): 

1D Array with dimension of 2 (every element pointing to an Point). 
Direction is given through first Object to the second. 
 

  
Planar Convex Hull (Polygon): 

A set of ordered points which specify vertices of the polygon. 
 
 
 
 
 
 
 
 
 
Algorithms 
 
  • A Naive Approach
    • Procedure
Input: A set P of points in the plane 
output: A list of L containing the vertices of CH(P) in clockwise order 

E<-0 
for all ordered pairs (p,q) belonging to PxP with p not equal to q 

    do valid<-true 
    for all points r belonging to P not equal to p or q 
      do if r lies to the left of the directed line from p to q 
        then valid<-false.
    if (valid) then Add the directed edge pq to E.
From the set E of edges construct the L, sorted in clockwise order 
 
 		  
Question: How can we sort E to get L efficiently ? 
 
  • Naive Approach:
starting from the starting point of any edge e, check all the other edges to find the edge f clockwisely adjacent to e by test whether the starting point of f is equal to the end point of e. 

repeat it until the end point of f is the starting point of the first edge. 

time complexity O(n^2) 
 

  • Linear-time Approach
see the figure at right.		  
Points  Adjacent Edges
a A, E
b A, B
c B, C
d C, D
e A, E
f
g
.
.
 
Edge Points
A a,b
B b,c
C c,d
D d,e
E e,a
 
    • Time Complexity
  • (n^2-n) pairs of points are checked;
  • for each pair we look at (n-2) other points to see whether they all lie on the right side;
  • In total, running time is O(n^3);
 
 
 
 
 
 
 
 
  • Giftwrapping
    • Procedure
Let m be the point with the minimum x-coordinate; 
       S be the set of points in the plane. 
Initialize p<-m, q not equal to p. 

Repeat  

    for all t belonging to S other than p, q do 
      if t is right of pq then 
        q<-t;
      endif
    endfor 
    output q 
    swap p and q
until p=m 
 
 

 
    • Time Complexity
     
O(nh)
where n is the number of all points 
           h is the number of points on convex hull
 
 
 
 
  • Incremental
    • Procedure
Input: A set P of points in the plane 
output: A list of L containing the vertices of CH(P) in clockwise order 

Sort the points lexicographically, resulting in a sequence p1,...pn. 

Put p1,p2 in a list Lupper, with p1 a the first point. 

for i=3->n 

    do Append pi to Lupper. 
      while Lupper contains more than two points and the last three points in Lupper do not make a right turn 
      do Delete the middle of the last three points from Lupper. 
Put pn,p(n-1) in a list of Llower, with pn as the first point 
for i=n-2 down to 1 
    do Append pi to Llower 
      while Llower contains more than 2 points and the last three points in Llower do not make a right turn 
      do Delete the middle of the last three points from Llower. 
Remove the first and the last point from Llower to avoid duplication of the points where the upper and lower hull meet. 
Append Llower to Lupper, and call the resulting list L. 

return L 
 

  
    • Time Complexity
     
  • Points sorting takes O(nlogn) time.
 
  • for loop is executed a linear number of times (O(n)).
    • while loop is executed at least once.
 
  • Extra steps due to deleting points are restricted to O(n)
 
  • In total its time complexity is O(nlogn) 
  
 
 
 
 
 
 
 
 
 
 
  • Divide-Conquer
    • Procedure
A global problem is divided into (smaller) subproblems. These subproblems are recursively conquered, or solved, and their solutions married, or recombined, into a solution for the original (larger) problem. 
 
 		  
Base case: one point 
Combination strategy: see the right figure 
    • Time Complexity
Analogous to well known divide-conquer method in sorting problem, its time complexity is O(nlogn).
 
 
 
 
 
 
  • Online Update
    • Procedure
Input: An existing convex hull with h vertices and a newly added point p. 
Output: A new convex hull updated with the new point p. 

Traveling along the old clockwisely directly convex hull and test every edge, delete the edge that will make a left turn to reach the new point p. 

Add two new edges from the new point p to the two ends of rest of edges. 

  
    • Time Complexity
     
 
O(h) 
 , where h is the number of edges of the old convex hull 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
Degeneracies & Robustness 
 
  • Degeneracies:
 
    • Sources: some special cases ,for examples
      • More than one points have the same x or y coordinate or both.
     
      • Three points lie on a straight line when checking left/right turn.
       
    • Solutions:
     
        Degenerate cases can almost always be handled by reconsidering the geometry of the problem and integrating special cases with the general case.
 
  • Robustness
 
    • Sources: 

      •  
      • rounding errors due to floating point arithmetic might distort outcomes of tests.
 
    • Solutions:

      •  
      • Use a package providing exact arithmetic. But it will reduce the speed.
      • Adjust algorithms to detect inconsistencies and take appropriate actions to avoid crashing the problem and give an acceptable output even though it is not exact.
 
 		  
 
 

   Symbolically: 
   2+0.000001=2.000001 

   For a floating point computing system with a precision   of 5 digits: 
   2+0.000001=2.00000 
 
 

  
 
 
 
 
 
 
 
 
 
 
 
 
An Application: Half-Space Intersection 
How to obtain the intersection of  half spaces defined by a set of lines ? 

Construct a dual space by mapping a line Ax+By-1=0 into a point(A,B). 

All lines are mapped into points in the dual space. The half-space  intersection corresponds to the convex hull in the dual space. 

Solve this planar convex hull problem with the methods we just talked about above. 

Mapping the convex hull back into the primal space to obtain the solution of the original problem.