Search code examples
algorithmgeometrycomputational-geometryconvex-hullconvex

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?

Solution

  • 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.