1 of 13

Convex Hull

Presented by

M.Jeevana Sujitha

Asst Professor

Dept of CSE,SRKR Engineering College

2 of 13

What is Convex Hull?

  • The convex hull of a set of points in a Euclidean space is the smallest convex polygon that encloses all of the points. 

​

Dept of CSE,SRKR Engineering College

3 of 13

What is Convex Hull?

  • The convex hull of a set S of points in the plane is defined to be the smallest convex polygon ,containing all points of S[ A polygon is defined as convex if for any two points p1 and p2 inside the polygon , the directed line segment from p1 to p2 denoted <p1,p2> is fully contained in the polygon]

Dept of CSE,SRKR Engineering College

4 of 13

Convex Hull: Divide & Conquer

  • Preprocessing: sort the points by x-coordinate
  • Divide the set of points into two sets A and B:
    • A contains the left ⎣n/2⎦ points,
    • B contains the right ⎡n/2⎤ points
  • Recursively compute the convex hull of A
  • Recursively compute the convex hull of B
  • Merge the two convex hulls

Dept of CSE,SRKR Engineering College

5 of 13

Convex Hull: Divide & Conquer

  • Divide the points into two approximately equal halves CHA(LEFT –PART) and CHB(RIGHT-PART)

Dept of CSE,SRKR Engineering College

6 of 13

Convex Hull: Divide & Conquer

  • CONQUER: Compute convex hull for left and right halves

​

​

​

​

​

​

  • COMBINE:Left and Right convex HULL

are combined by using lower tangent

and upper tanget

Dept of CSE,SRKR Engineering College

7 of 13

Convex Hull: Divide & Conquer

  • Start with the right-most node of left-convex HULL

consider it as V

  • Start with the left-most node of right –convex HULL

consider it as W

Dept of CSE,SRKR Engineering College

8 of 13

Convex Hull: Divide & Conquer

Dept of CSE,SRKR Engineering College

performed in left convex HULL perform same in right convex HULL

9 of 13

Convex Hull: Divide & Conquer

Dept of CSE,SRKR Engineering College

Here W is the lower tangent value so break from the loop

Select the left most point in the right convex HULL i.e W

10 of 13

Convex Hull: Divide & Conquer

Dept of CSE,SRKR Engineering College

Select the rightmost point in the left convex Hull as V

Select the leftmost point the right convex Hull as W

11 of 13

Convex Hull: Divide & Conquer

Dept of CSE,SRKR Engineering College

12 of 13

Convex Hull: Divide & Conquer

Dept of CSE,SRKR Engineering College

Once the lower and upper tangents are computed the merging is completed

13 of 13

Convex Hull: Divide & Conquer

Dept of CSE,SRKR Engineering College

Solving the recurrence relation using Substitution method