Part of list:

Quick-Hull: A quick-sort like algorithm for convex hull

Quick-Hull: A quick-sort like algorithm for convex hull[ Edit ]

**Visualization**:

**The algorithm**:

- Find the points with minimum and maximum x coordinates. These will always be part of the convex hull.
- The line formed by these points divide the remaining points into two subsets, which will be processed recursively.
- Determine the point, on one side of the line, with the maximum distance from the line. This point will also be part of the convex hull. The two points found before along with this one form a triangle.
- The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.
- Repeat the previous two steps on the two lines formed by the triangle (not the initial line).
- Stop when no more points are left.

**Run-time**:

The algorithm has a worst case run-time of O(n^2) and an average case run-time of O(n log n). However, note that it is possible for people to design data for which this algorithm will take O(n^2) time. For example, the algorithm has a bad run time when the points are located on the circumference of a circle.

Source: Wikipedia.

Read more…(188 words)

Mark as completed

Part of lists:

Previous

Graham Scan: O(n log n) convex-hull algorithm

About the contributor:

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Loading…

Have a question? Ask here…

Post

Part of list:

Quick-Hull: A quick-sort like algorithm for convex hull

Contributor

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.