Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

1 Answer

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

share|improve this answer
    
By "angles", you means "slopes", of course. Trigonometry is anathema to actual implementation. –  JeffE Apr 11 '12 at 7:54
    
@JeffE: True.$ $ –  joriki Apr 11 '12 at 9:08
    
@joriki, sorry, I don't get the hint. The slope just tell me which vertex will be next, but for the next vertex all already computed slopes are irrelevant, it looks like not just slopes plays am important role, also lengths. –  com Apr 11 '12 at 17:32
    
@com: The slope tells you more than which vertex will be next. You can use the slope to divide the points into two groups on either side of the line to the starting point. Points in one of these two groups can't be part of the convex hull. By the way, there's no need to ping me here; the post owner automatically gets notified of comments under a post. –  joriki Apr 11 '12 at 17:46
    
Sorry, I am still don't get it. At every vertex all other vertices are on one(left) side of the line going through the vertex. –  com Apr 11 '12 at 18:51
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.