I am trying to solve taks 2 from exercise 3.4.1 from Computational Geometry in C by Joseph O'Rourke. The task asks to improve Gift Wrapping Algorithm for building convex hull for the set of points.

Exercise: During the course of gift wrapping, it's sometimes possible to identify points that cannot be on the convex hull and to eliminate them from the set "on the fly". work out rules to accomplish this. What is a worst-case set of points for your improved algorithm.

The only thing I came with is we can eliminate all point that already form a convex hull boundary from the candidate list. This can give us the slight improvement $O(\frac{hn}{2})$ instead of $O(hn)$, which is in term of Big-O notation actually the same.

After a little bit of searching I found that improvement can be made by ray shooting, but I don't understand how to implement ray shooting to our case (all points are not sorted and don't form a convex hull, therefore there is no efficient search for vertex that can be taken by ray shooting).

If you have any idea how to improve gift wrapping algorithm, I'll appreciate sharing it with us.

Thanks!

-
Note that the exercise does not say "improve the asymptotic complexity of gift wrapping," it just asks for avoiding unnecessary computations. – Joseph O'Rourke Apr 12 '12 at 0:04

@JeffE: True. – joriki Apr 11 '12 at 9:08