0
$\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
    By "angles", you means "slopes", of course. Trigonometry is anathema to actual implementation.2012-04-11
  • 0
    @JeffE: True.$ $2012-04-11
  • 0
    @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.2012-04-11
  • 0
    @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.2012-04-11
  • 0
    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.2012-04-11
  • 0
    @com: I don't know what you mean by "the line going through the vertex". There are infinitely many lines going through a vertex. I was talking about the line from the vertex to the starting point. By the starting point, I mean the very first vertex at which you started the algorithm, the beginning of the convex hull that you're constructing.2012-04-11
  • 0
    but the starting point is the point with lowest y-coordinate2012-04-12
  • 0
    @com: This interaction is very inefficient. Don't you think it would make sense to tell me where you see the contradiction between the starting point being the point with the lowest $y$-coordinate and what I wrote?2012-04-12
  • 0
    There is no contradiction, please make it clear for me, how to determine the group of points which can't be a part of the convex hull.2012-04-13
  • 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