Convex hull: known number of points but not points itself

1
votes

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?

2
algorithmgeometrycomputational-geometryconvex-hullconvex
as a side note, nC6 is O(n^6), not O(n) – user3235832
Check out en.wikipedia.org/wiki/Convex_hull_algorithms – Max Zuber
How about first checking here en.wikipedia.org/wiki/Convex_hull_algorithms ? Edit: ninja'd – Vesper
the convex hull is unique so why are you talking about 6 points etc just look up the algoritthm and execute it - its a minor problem if you have 1000 points or 10000 points it cannot be more than O(n^2) – gpasch
Checking a 6-set takes O(N), so the total complexity would be O(N^7). Generally speaking, O(N^7) is just unthinkable, except for tiny N. For N=10, N^7 is already ten millions. For N=100, it is a hundred thousand billions. – Yves Daoust

2 Answers

5
votes

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.

1
votes

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.