1
$\begingroup$

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!

  • 0
    Note that the exercise does not say "improve the asymptotic complexity of gift wrapping," it just asks for avoiding unnecessary computations.2012-04-12

1 Answers 1

1

Hint: You're already computing the angles of the lines from the current point to all other points. What does the relationship of these angles to the angle of the line to the starting point tell you? (This also doesn't improve the time complexity of the algorithm.)

  • 0
    @com: (The word "but" usually indicates a contradiction or at least some form of tension between what went before and what comes after.) After you've built part of the convex hull, some of the remaining points are inside what you've already built and some are outside. The ones on the inside will not become part of the convex hull, so you can drop them, and you can identify them by which side of the line from the current point to the starting point they're on.2012-04-13