2
$\begingroup$

I have an alternative algorithm for the problem of finding a convex hull for a collection of points. It is somewhat similar but not the exact of Graham scan.

  1. Find a point that is guaranteed to be inside the convex hull, this can be done by finding the line connecting the left most and right most points. And then pick a point between the two end points.
  2. Use the point in (1) as origin and convert all other points into polar coordinate.
  3. Sort all other points in counter clockwise motion and iterate (same way one orders angles in radian of the unit circle)
  4. When the point has y coordinate higher than the origin, then the tangent value between the current point and the last point in the convex hull has to go up compared to the last tangent value. If not we need to wrap the previous points to some earlier point to satisfy this requirement.
  5. When the point has y-coordinate lower than the origin, then the tangent value has to go down.

The running time is $O(n\log n)$ because that is of sorting and for each point in step 4 and 5, one only needs $O(\log n)$ to search for appropriate previous point.

My question is this seems much simpler than Graham scan. Is there any problem in it (correctness) other than the running time in which iteration in Graham scan is only linear while it is $O(n\log n)$ here

$\endgroup$
  • 1
    $\begingroup$ What have you tried to prove that it works? Also, step 4 is not so precisely specified and "tangent value" is a bit unclear. $\endgroup$ – Louis Aug 29 '14 at 9:14
  • $\begingroup$ @Louis From the description, the only fuzzy part I can see is in the boundary cases where iteration moves between 4 and 5 above. Other than that, if a point cannot fall outside the hull, the hull is convex because tangent values are all monotonic. $\endgroup$ – InformedA Aug 29 '14 at 9:32
  • 1
    $\begingroup$ There is not really a question here, then. It's correct, the description is sharp, and everybody understands all the terms. $\endgroup$ – Louis Aug 29 '14 at 9:53
  • $\begingroup$ The point found in step 1 can be on the boundary of the convex hull. If that is "inside" the convex hull why not pick a random point? $\endgroup$ – invalid_id Aug 29 '14 at 10:04
  • $\begingroup$ @invalid_id In that inside case, all other points will be either under or above the chosen point. It's still good. You can't choose random point because you can't have what I said above with completely random. $\endgroup$ – InformedA Aug 29 '14 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.