JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

1 of 11

Quick Hull

Presented by

M.Jeevana Sujitha

Asst Professor

Dept of CSE,SRKR Engineering College

2 of 11

What is Quick Hull?

Quick Hull works on the principle of quick sort .select small point and the largest point on the x-coordinate

Dept of CSE,SRKR Engineering College

3 of 11

What is Quick Hull?

Here the smallest point is p1(b) and largest point is p2(k)
P1 and p2 are part of a convex HULL

The other points on the convex HULL are divided based on the line segment

Dept of CSE,SRKR Engineering College

4 of 11

What is Quick Hull?

The points above the line segment are called as upper Hull
The points below the line segments are called as lower Hull

Dept of CSE,SRKR Engineering College

5 of 11

What is Quick Hull?

The points above the line segment are called as upper Hull
The points below the line segments are called as lower Hull
The convex hull of upper Hull

And lower Hull is computed using

Divide and Conquer Strategy

The union of these two Hull make

The complete complete convex Hull

Dept of CSE,SRKR Engineering College

6 of 11

Compute Upper convex Hull

Select one point P from the Upper Hull.
Calculate area formed by P,P1,P2
Select another point(d) consider d as p and

Compute area formed by p(d),p1,p2

Select another point(a) consider a as p and

Compute area formed by p(a),p1,p2

Dept of CSE,SRKR Engineering College

7 of 11

Compute Upper convex Hull

Here point d has largest area .we are selecting the d because most of the points comes under these area.

All the points inside area can be ignored,and

Consider point d as p3 point which belong to convex

Hull

Dept of CSE,SRKR Engineering College

8 of 11

Compute Upper convex Hull

Dept of CSE,SRKR Engineering College

9 of 11

Compute Lower convex Hull

Dept of CSE,SRKR Engineering College

10 of 11

Quick Hull

Dept of CSE,SRKR Engineering College

11 of 11

Time Complexity

Dept of CSE,SRKR Engineering College