Talk:Graham scan

From Wikipedia, the free encyclopedia

A Wikipedian removed Graham scan from the good article list. There are suggestions below for improving areas to satisfy the good article criteria. Once the objections are addressed, renominate the article as a good article. If you disagree with the objections, you can seek a review. Removal date: No date specified. Please edit template call function as follows: {{DelistedGA|insert date in any format here}}

would be interesting to add to this article what its practical applications are. Graham 23:16, 15 Mar 2004 (UTC)

Are they different from those of the result, the convex hull? Frencheigh 22:59, 18 Mar 2004 (UTC)

Yes, of course. Why would I need to find the convex hull of a set of points? In other words, what is the practical application of this? Graham 23:57, 18 Mar 2004 (UTC)

Well, it would make more sense to put those on the Convex hull page, I think (where there are already some sort of vague applications). Frencheigh 01:18, 19 Mar 2004 (UTC)

On the Wikipedia:Featured article candidates page I wrote that the article contains subtle errors. They do not invalidate the main idea, but may lead to confusion. Most of them are related to treating of degenerate cases. The best way to deal with them is to break the description into four parts.

1. case of points in general position, for the most transparent exposition of the main idea
2. hints for treating degenerate cases (something about 3 points on a line is already mentioned)
3. hints for treating precision of real-life computer computations
4. hints for speed-up of particular steps

Still another problem is in description of computational complexity. While the general idea is correct, the description is wrong. In fact, it could be a good idea to illustrate the method of amortized analysis in computational complexity theory by applying it to gracham's scan. I promised to fix the article, but unfortunately I am seriously distracted from work in wikipedia now, sorry. Mikkalai 05:20, 21 Mar 2004 (UTC)

Then is the "the loop", actually, as the article says, O(n)? If so, would the use of radix sort make the algorithm O(n), rather than O(n log n)... Frencheigh 22:00, 6 Jun 2005 (UTC)

You cannot sort in O(n), so no. But yes, the loop is O(n). — Timwi 15:23, 9 Jun 2005 (UTC)

Please keep in mind that you can use radix sort usefully, if point coordinates are integers and scaled to range [0, O(n)]. In particular, since Graham scan sorts the angles, you are nowhere. However if you do have points with "good" integer coordinates, there are variants of Convex Hull algorithm that do better. Also, the fact that Gracham's requires computation of angles, the algorithm, being nice theoretically, in practice has problems with robustness. mikka (t) 17:53, 9 Jun 2005 (UTC)

The range "[0, O(n)]" doesn't make any sense. Any finite number n of points is always in the interval [-kn, kn] for some k. Graham's scan does not require computation of any angles. — Timwi 19:51, 9 Jun 2005 (UTC)

The range does make sense, if one recalls that the whole "O" terminology makes sense only in an asymptotic case, i.e., when we have an infinite (say, reasonably large) series of problem instances. If we speak about one isolated problem, then all algorithhms are O(1). Graham scan does require computation of either angles (as written in the article) or comparison of tangent values (if one is smart enough), which has the same problem with real numbers (usage of integers leads to overflow problems). The version that does not require angular sort has a different name. mikka (t) 20:28, 9 Jun 2005 (UTC)

I have no idea what your interval is supposed to mean. This is an algorithm that is applied to one set of points, not a sequence of sets of increasing size. Regardless, no matter what you do, you can't sort in O(n). That's a fact. — You do not need to use "real" (floating-point) numbers anywhere in Graham scan (unless of course the input is already floating-point). Look at the fourth paragraph in the algorithm section. — Timwi 08:33, 11 Jun 2005 (UTC)

---

A diagram indicating which points have been labelled p1 p2 and p3 when calculating the cross product would be cool, i dont have the time atm, maybe later 61.68.3.133 11:13, 3 January 2006 (UTC)

[edit] Delisted GA

There are no images, there are no references. slambo 17:28, 23 October 2005 (UTC)

I added an illustration. It isn't very cute, but illustrates the main point of the algorithm. Imbaczek 22:52, 21 January 2006 (UTC)

[edit] Ref: Note 1

When does the check mentioned in Note 1 come into play? I dont think this check is necessary.

[edit] collinear points

The convex hull article defines the problem as the minimal set. If this is true, then it does indeed matter whether you throw out a point when it's between two others; you must.