Part of course:

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

NaN.

Part of course: Competitive Programming: From Beginner to Expert

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

Previous

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

Part of courses:

About the contributor:

Keshav DhandhaniaFormer TopCoder India #1. DM me for 1-on-1 mentorship (paid)

100%

Loading…

Have a question? Ask here…

Post

Part of course:

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

Ready to join our community?

Sign up below to automatically get notified of new courses, get **reminders** to finish ones you subscribe to, and **bookmark** lessons 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.

Popular Courses

New Courses

About Us

Get in touch

Copyright 2016-18, Compose Labs Inc. All rights reserved.