CODEWITHSUNDEEP
algorithmgeometrycomputational-geometryconvex-hullconvex
今天春天
今天春天

Reputation: 993

Convex hull: known number of points but not points itself

I need to find an algorithm which computes a convex hull from a given set of points S of size n. I know that there are exactly 6 points from S which form the convex hull.

What is the best and most efficient way to compute this?

I thought about generating all possible combinations of points from S (which would be n choose 6 points) which would take O(n^6) and then check if this is a convex hull, which would take O(n) but lead into a very bad total runtime. There must be a better way. Any hints?

Upvotes: 1

Views: 354

Answers (2)

MathBunny
MathBunny

Reputation: 956

As already suggested, the Jarvis March / Gift-wrapping algorithm is very quick in this instance, because the time complexity is O(nh), compared with O(nlogn) in Graham Scan.

The only algorithm that comes to thought that would be quicker would be Chan's algorithm that runs in O(nlogh), but since h is very small the difference would be marginal. Read more about Chan's algorithm here.

Upvotes: 1

Abhishek Bansal
Abhishek Bansal

Reputation: 12705

If only 6 points lie on the convex hull then Jarvis March or the Gift-wrapping algorithm would be very efficient. It runs in O(nh) time where h is the number of points on the convex hull.

Upvotes: 5

Related Questions