View source for Talk:Graham scan

{{ArticleHistory
|action1=GAR
|action1date=23 October 2005
|action1result=delisted
|action1oldid=25348950

|action2=GAN
|action2date=23:57, 11 February 2008 (UTC)
|action2result=not listed
|action2oldid=190373550

|currentstatus=DGA
}}
{{WikiProject banner shell|class=C|1=
{{WikiProject Computer science}}
}}

== Pseudocode ==

Look like the pseudocode was written by students that don't really understand the book they are reading ... !!!  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2A01:CB00:220:9300:51AE:D4BE:95EC:AD2D|2A01:CB00:220:9300:51AE:D4BE:95EC:AD2D]] ([[User talk:2A01:CB00:220:9300:51AE:D4BE:95EC:AD2D#top|talk]]) 12:58, 10 February 2019 (UTC)</small> <!--Autosigned by SineBot-->

==Error on this page==
On couple places were <nowiki><math></nowiki> tag is used there is an error:

"Failed to parse (Cannot write to or create math output directory): (x_1,y_1) , Failed to parse (Cannot write to or create math output directory): (x_2,y_2)"

I've copied the document's code into the sandbox, and there worked fine...  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/78.3.221.164|78.3.221.164]] ([[User talk:78.3.221.164|talk]]) 12:53, 23 January 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

==Applications==
would be interesting to add to this article what its practical applications are. [[User:GRAHAMUK|Graham]] 23:16, 15 Mar 2004 (UTC)

Are they different from those of the result, the convex hull? [[User:Frencheigh|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? [[User:GRAHAMUK|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). [[User:Frencheigh|Frencheigh]] 01:18, 19 Mar 2004 (UTC)

==Subtle errors==
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.
# case of points in [[general position]], for the most transparent exposition of the main idea
# hints for treating [[degenerate case]]s (something about 3 points on a line is already mentioned)
# hints for treating [[precision]] of real-life computer computations
# 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. [[User:Mikkalai|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)... [[User:Frencheigh|Frencheigh]] 22:00, 6 Jun 2005 (UTC)

:: You cannot sort in O(n), so no. But yes, the loop is O(n). &mdash; [[User:Timwi|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. [[user:mikkalai|mikka]] [[user talk:mikkalai|(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. &mdash; [[User:Timwi|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. [[user:mikkalai|mikka]] [[user talk:mikkalai|(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. &mdash; 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. &mdash; [[User:Timwi|Timwi]] 08:33, 11 Jun 2005 (UTC)
::::::: Timwi, you should look up Radix sort. The O(n.log n) bound only applies to comparison based sorts. [[Special:Contributions/99.74.82.46|99.74.82.46]] ([[User talk:99.74.82.46|talk]]) 03:08, 22 October 2009 (UTC)

:Radix sort on n-bit integers makes n passes over the data. Quicksort makes log(n) passes with high probability. So for input size less than 2^n, quicksort will do less work than radix sort, even on integers. For 32-bit integers the break-even point is 16 GiB, for 64 bit integers it is more than what is addressable on x86-64. So while you are technically correct, it is highly misleading to say radix-sort has better complexity compared to other algorithms. [[Special:Contributions/62.163.252.147|62.163.252.147]] ([[User talk:62.163.252.147|talk]]) 17:41, 29 May 2024 (UTC)

==Diagram request==

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 [[User:61.68.3.133|61.68.3.133]] 11:13, 3 January 2006 (UTC)

== Delisted GA ==
There are no images, there are no references.  [[User:Slambo|slambo]] 17:28, 23 October 2005 (UTC)

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

== Ref: Note 1 ==

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

== Angle comparison ==
Use of monotonic function is OK but
"slope of the line may be used"
slope may cause problems when vectors are perpendicular or nearly perpendicular</br>
Is comparison by angle only enough ?</br>
In case of collinear points comparison by distance (polar radius) can be useful</br>

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

: A convex set includes ''all Euclidean points'' inside convex boundaries.  There is an infinite number of them, not only those you explicitly specified to ''build'' the convex hull.  So the important thing is the boundary, not in how many points you define that boundary.  [[User:SnakeScaly|SnakeScaly]] ([[User talk:SnakeScaly|talk]]) 16:31, 12 May 2009 (UTC)


Considering the following case it appears (some) aligned points have to be removed:
* p1 = { -1 -1 }
* p2 = { 1 0 }
* p3 = { 0.5 0.5 } <- turns left (from the two previous)
* p4 = { 0 0 }     <- turns left
* p5 = { 1 1 }     <- aligned
* p6 = { 0 1 }     <- turns left
If colinear points are accepted the result of the devised algorithm would be: <br />
{ p1, p2, p3, p4, p5, p6 } <br />
However the convex hull is: <br />
{ p1, p2, p5, p6 }<br />
--[[User:Mboucher42|Mboucher42]] ([[User talk:Mboucher42|talk]]) 16:03, 4 April 2013 (UTC)

CLRS pseudocode suggests to delete collinear points except of the farthest from p0
According to pseudocodes from other books sorting also by distance from p0 will be enough

== Failed Good Article review ==

'''[[Wikipedia:Good article nominations|GA]] review – see [[WP:WIAGA]] for criteria'''
{{#if:This article needs significant improvement to meet the [[Wikipedia:Good article criteria|Good article criteria]].  The major areas where it is lacking are breadth of coverage and overuse of jargon.  Though it is difficult for highly technical articles such as this, recall that ''all'' wikipedia articles must strive to be accessible for a general audience.|<hr width=50%>This article needs significant improvement to meet the [[Wikipedia:Good article criteria|Good article criteria]].  The major areas where it is lacking are breadth of coverage and overuse of jargon.  Though it is difficult for highly technical articles such as this, recall that ''all'' wikipedia articles must strive to be accessible for a general audience.|}}
#Is it '''reasonably well written'''?
#:A. Prose quality: {{GAList/check|n}} 
#:: {{#if:The explanation of the algorithm is very difficult to follow.  I suggest starting by clearly defining the goal of the algorithm, which can then be referenced during the explanation.  Also, the image looks good, but it and the textual explanation need to mesh better, with the text referencing steps clearly indicated in the image.|The explanation of the algorithm is very difficult to follow.  I suggest starting by clearly defining the goal of the algorithm, which can then be referenced during the explanation.  Also, the image looks good, but it and the textual explanation need to mesh better, with the text referencing steps clearly indicated in the image.|}}
#:B. [[Wikipedia:Manual of Style|MoS]] compliance: {{GAList/check|n}}
#:: {{#if:This is where the article needs the most improvement.  All technical terms which are ''necessary'' to the points being made must be sufficiently explained ''in this article'' so that a general reader can follow the prose ''without'' having to follow wikilinks.  For example, the article begins "The Graham scan is a method of computing the convex hull of a given set of points in the plane with time complexity O(n log n)", yet the terms "convex hull", "plane", "time complexity" or "O(n log n)" aren't even cursorily explained anywhere in the article.  For more guidelines and suggestions on avoiding and clarifying jargon, see [[wikipedia:Explain jargon]], [[Wikipedia:Make technical articles accessible]], and [[Wikipedia:Technical terms and definitions]].<br>Secondarily, the pseudocode section needs to be brought up to [[wikipedia:manual of style|manual of style]] standards. The "Note:", "Note2:" convention, for example, should be changed to paragraph format.|This is where the article needs the most improvement.  All technical terms which are ''necessary'' to the points being made must be sufficiently explained ''in this article'' so that a general reader can follow the prose ''without'' having to follow wikilinks.  For example, the article begins "The Graham scan is a method of computing the convex hull of a given set of points in the plane with time complexity O(n log n)", yet the terms "convex hull", "plane", "time complexity" or "O(n log n)" aren't even cursorily explained anywhere in the article.  For more guidelines and suggestions on avoiding and clarifying jargon, see [[wikipedia:Explain jargon]], [[Wikipedia:Make technical articles accessible]], and [[Wikipedia:Technical terms and definitions]].<br>Secondarily, the pseudocode section needs to be brought up to [[wikipedia:manual of style|manual of style]] standards. The "Note:", "Note2:" convention, for example, should be changed to paragraph format.|}}
#Is it '''factually accurate''' and '''[[Wikipedia:Verifiability|verifiable]]'''?
#:A. References to sources: {{GAList/check|n}} 
#:: {{#if:|{{{2acom}}}|}}
#:B. Citation of reliable sources where necessary: {{GAList/check|n}} 
#:: {{#if:Only a single in-line reference at the end of the first sentence.  To be a "well-referenced" article, at minimum, the article must provide in-line citations from reliable sources for statistics, counter-intuitive  statements that could be challenged.|Only a single in-line reference at the end of the first sentence.  To be a "well-referenced" article, at minimum, the article must provide in-line citations from reliable sources for statistics, counter-intuitive  statements that could be challenged.|}}
#:C. [[Wikipedia:No original research|No original research]]: {{GAList/check|???}}
#:: {{#if:The pseudo-code example should be attributed to a referenced source, otherwise it qualifies as original research.|The pseudo-code example should be attributed to a referenced source, otherwise it qualifies as original research.|}}
#Is it '''broad in its coverage'''?
#:A. Major aspects: {{GAList/check|n}} 
#:: {{#if:As mentioned already on the talk page, to be considered broad it coverage this article would need to include a section on the useful applications of the Graham scan algorithm.  Yes, this will mean redundancy with [[convex hull]], but that's no a problem.  In fact, in order to improve the accessibility, an entire section (briefly) explaining what a convex hull is would be useful, and applications would fit well there.  Another subject that could be explored is where Graham scan fits in the history of convex hull algorithm.|As mentioned already on the talk page, to be considered broad it coverage this article would need to include a section on the useful applications of the Graham scan algorithm.  Yes, this will mean redundancy with [[convex hull]], but that's no a problem.  In fact, in order to improve the accessibility, an entire section (briefly) explaining what a convex hull is would be useful, and applications would fit well there.  Another subject that could be explored is where Graham scan fits in the history of convex hull algorithm.|}}
#:B. Focused: {{GAList/check|y}}
#:: {{#if:|{{{3bcom}}}|}}
#Is it '''[[WP:NPOV|neutral]]'''?
#:Fair representation without bias: {{GAList/check|y}}
#:: {{#if:|{{{4com}}}|}}
#Is it '''stable'''?
#: No edit wars, etc: {{GAList/check|y}}
#:: {{#if:|{{{5com}}}|}}
#Does it '''contain [[Wikipedia:Images|images]]''' to illustrate the topic?
#:A. Images are copyright tagged, and non-free images have [[Wikipedia:Image_description_page#Use_rationale|fair use rationales]]: {{GAList/check|y}} 
#:: {{#if:|{{{6acom}}}|}}
#:B. Images are provided where possible and appropriate, with [[WP:CAP|suitable captions]]: {{GAList/check|y}}
#:: {{#if:|{{{6bcom}}}|}}
#'''Overall''': 
#:Pass or Fail: {{GAList/check|n}}
#:: {{#if:Once the issues above have been addressed, I suggest the article be taken to [[wp:peer review|peer review]] for feedback before renomination as a good article.|Once the issues above have been addressed, I suggest the article be taken to [[wp:peer review|peer review]] for feedback before renomination as a good article.|}}
--[[User:Jwanders|jwanders]]<sup>[[User_talk:Jwanders|Talk]]</sup> 04:27, 12 February 2008 (UTC)

===Delisted - and good for it ===

Obviously the article was not reviewed by an expert in [[computational geometry]]. The description of the algorithm has numerous problems I will not even start to list here. I will better rewrite it in my free time. It is OK-ish for the first read about the algorithm, but ... `'[[user:mikkalai|Míkka]][[user talk:mikkalai|>t]] 04:54, 12 February 2008 (UTC)

== Cross product ? ==

[[Cross product]] is only defined in 3- and 7-dimensional space.  What you use here to test for collinearity/turn direction is a [[dot product]] with one vector turned 90 degrees.  So for points '''p'''<sub>1</sub>, '''p'''<sub>2</sub> and '''p'''<sub>3</sub>:

<math>\mathbf{u} = \mathbf{p}_2 - \mathbf{p}_1</math>

<math>\mathbf{v} = \mathbf{p}_3 - \mathbf{p}_1</math>

<math>ccw = \mathbf{u}_\perp \cdot \mathbf{v}</math>

Since <math>\mathbf{u}_\perp = \begin{vmatrix}u_x & u_y\end{vmatrix}_\perp = \begin{vmatrix}-u_y & u_x\end{vmatrix}</math>, you get the final formula:

<math>ccw = \mathbf{u}_\perp \cdot \mathbf{v} = u_{\perp{}x} v_x + u_{\perp{}y} v_y = -u_y v_x + u_x v_y = (p_{2x}-p_{1x})(p_{3y}-p_{1y}) - (p_{2y}-p_{1y})(p_{3x}-p_{1x})</math>

[[User:SnakeScaly|SnakeScaly]] ([[User talk:SnakeScaly|talk]]) 16:31, 12 May 2009 (UTC)

_______________________________________________________________________________________________________________________________________________________  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/196.30.31.182|196.30.31.182]] ([[User talk:196.30.31.182|talk]]) 10:21, 27 October 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

Whoever wrote the above, interpret the cross product of <math> \mathbf{u} </math> x <math> \mathbf{v} = (u_x, u_y) </math> x <math> (v_x, v_y) </math>  in 2D as <math> u_x v_y - u_y v_x </math>.

If <math> u_x v_y - u_y v_x < 0 </math> then <math> \mathbf{u} </math> is anti-clockwise from <math> \mathbf{v} </math> and if <math> u_x v_y - u_y v_x > 0 </math> then <math> \mathbf{u} </math> is clockwise from <math> \mathbf{v} </math>.

Clearly, if <math> u_x v_y - u_y v_x = 0 </math>, the two vectors are parallel.  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/196.30.31.182|196.30.31.182]] ([[User talk:196.30.31.182|talk]]) 10:19, 27 October 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

__________________________________

What really is used are affine coordinates. That is, the quantity computed is the 3x3-determinant or triple product of the vectors <math>(1,x_A,y_A)</math>, <math>(1,x_B,y_B)</math> and <math>(1,x_C,y_C)</math>. This determinant is positive if the planar triangle ABC is positively, counter-clockwise oriented or the curve A-B-C has a left turn. And negative for clockwise or a right turn. Using row- or column-operations one arrives at a 2x2-determinant with the same value as the 3x3-determinant and giving the expression in the article.
:<math>
\begin{vmatrix}
1&x_A&y_A\\
1&x_B&y_B\\
1&x_C&y_C
\end{vmatrix}
=
\begin{vmatrix}
1&x_A    &    y_A\\
0&x_B-x_A&y_B-y_A\\
0&x_C-x_A&y_C-y_A
\end{vmatrix}
=
\begin{vmatrix}
x_B-x_A&y_B-y_A\\
x_C-x_A&y_C-y_A
\end{vmatrix}
</math>
--[[User:LutzL|LutzL]] ([[User talk:LutzL|talk]]) 14:38, 14 June 2012 (UTC)

== Animating GIF image ==

I was working on some personal web pages, and I made an animating gif image of the Graham scan process, I thought it might add to the quality of the page to include it. Here is a link to it, feel free to use it if someone cares to edit the main page.

[http://upload.wikimedia.org/wikipedia/en/b/b8/GrahamScan.gif link image]  <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:David Ashley|David Ashley]] ([[User talk:David Ashley|talk]] • [[Special:Contributions/David Ashley|contribs]]) 21:22, 8 October 2009 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Pseudo-code example is confusing ==

I'm trying to implement this algorithm in the Ruby language for use inside Google's SketchUp. I think I understand the algorithm itself, but I'm having trouble deciphering the pseudo-code.

My first problem is with the array. Do the indices go a) from one to the number of points, b) from zero to the number of points minus one, or c) something else?  For example, when it refers to points[1] during the first step (finding the lower-left point) is it referring to the first point in the list, or the second?  And then, when it refers to points[0], is that a new point that was added to the front of the list?

Also, what does "We want points[0] to be a sentinel point that will stop the loop." mean? Is there supposed to be a test that will exit the for loop early? Is this "sentinel point" even necessary? Which point is it and where is it supposed to be inserted in the array?

No offense to the original author (nor to Sedgewick or Wayne) but could someone else who understands this algo make some new (or clarify the existing) pseudo-code?

Thanks a lot to anyone who has worked on or will work on this article (except Altenmann, who is a ***) (all the other references to this algo I could find are even less comprehensible!)

[[Special:Contributions/75.28.168.96|75.28.168.96]] ([[User talk:75.28.168.96|talk]]) 22:13, 27 October 2009 (UTC)
:Sorry, this is an encyclopedia, not student advisor. I deleted the pseudocode, because it is incorrect. If you need it for job, I am sure you will find numerous implementations of  the algorithm in the internet. If you need it for a student project, please read and understand an algorithm, and implement it yourself. If wikipedia is unclear, please read other books. Wikipedia is not the ultimate source of absolute wisdom, it is a tool to find information. - Altenmann [[user talk:Altenmann|>t]] 22:51, 27 October 2009 (UTC)

::I put the code back for two reasons:

::1) You obviously don't know why it's "incorrect", or you would have fixed it (though you ''are'' omniscient enough to know who I am and why I need the algorithm. Odd...).

::2) because I still have hopes that someone who ''does'' know what's wrong (which may be me, no thanks to you) will have something to fix, thus making Wikipedia better, rather than using it as his/her personal trolling grounds.

::[[Special:Contributions/75.28.168.96|75.28.168.96]] ([[User talk:75.28.168.96|talk]]) 00:02, 28 October 2009 (UTC)

For the psuedocode, it says "sort by polar angle".  Well is it sort by polar angle ascending as i gets higher or sort by polar angle descending as i gets higher?  <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Yamazon3|Yamazon3]] ([[User talk:Yamazon3|talk]] • [[Special:Contributions/Yamazon3|contribs]]) 03:09, 13 December 2011 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

Why not use the pseudocode from Cormen et al? Many other Wikipedia articles use pseudocode from that text, and it's very understandable.[[User:Dideler|Dideler]] ([[User talk:Dideler|talk]]) 06:34, 16 March 2012 (UTC)

== Speed up ==

"In order to speed up the calculations, it is not necessary to calculate the actual angle these points make with the x-axis; instead, it suffices to calculate the cosine of this angle: it is a monotonically decreasing function in the domain in question (which is 0 to 180 degrees, due to the first step) and may be calculated with simple arithmetic."

Having implemented this algorithm, I found a possible problem with this "speed up", regarding numerical stability near zero. Consider the angles 0 and say 1.0e-11; their cosines are 1 and 0.99999999999999999999995. Thus two angles within 1.0e-11 have cosines only 5.0e-23 apart, which may be considered equal to machine precision. In general, two small angles 0 and e will give cosines 0.5e^2 apart.

As far as I can tell, this optimisation isn't in the original paper, nor does it have its own ref. It's been in the article from the beginning, but originally referred to the "tangent" instead of cosine, which doesn't make sense at all. It also reeks of premature optimisation - this speed up won't affect the Big O performance of the operation, and it's unclear it would speed things up in general. For starters, calculating the angles is O(n), so in general not the bottleneck of an O(n log n) algorithm. Whilst atan2 may take extra CPU cycles, it's quite an assumption that this would be noticeable in most circumstances. Since there appears to be no reference, I propose removing it altogether to avoid confusing the issue. [[User:Mdwh|Mdwh]] ([[User talk:Mdwh|talk]]) 09:43, 11 July 2012 (UTC)

:Hi, but where do you get the angles from? The slope of the lines is computed first and is actually the tangens of the angle of the line, so "computing the tangens" or the cosine from it actually does not need to involve the actual angle at all. Also, per the german page, it is possible to use the oriented area formula to compare two points for greater angle wrt. a third point. AC has a greater angle than AB if ABC is positively oriented iff C is left of the line from A through B (see my comment above under "cross product"). Nevertheless, this special point has no place in an informal or motivational overview of the algorithm.--[[User:LutzL|LutzL]] ([[User talk:LutzL|talk]]) 14:29, 11 July 2012 (UTC)

: Basically, what [[User:LutzL|LutzL]] said. The whole point of the optimisation is that it’s possible to compare angles using integer arithmetic only (using the co-ordinates of the original points) without having to actually compute any angles or use any floating-point arithmetic at all. — [[User:Timwi|Timwi]] ([[User talk:Timwi|talk]]) 07:47, 3 December 2012 (UTC)

: In fact, the <code>ccw</code> function in the example implementation is the embodiment of this! There’s no floating-point arithmetic and no angle calculation in there. — [[User:Timwi|Timwi]] ([[User talk:Timwi|talk]]) 07:49, 3 December 2012 (UTC)

== Graham scan or Graham's scan? ==

The title is Graham scan, but the lead introduces it as Graham's scan. Throughout the article both versions are used. Which is correct? [[User:Ollieinc|<span style="font-family:sans-serif;color:#438fff">'''Ollie'''inc</span>]]&nbsp;([[User talk:Ollieinc|<span style="font-family:sans-serif;color:#438fff;">talk</span>]]) 09:37, 31 May 2017 (UTC)

== Parallelisation ==

The article claims that the linear phase of Graham's scan can be parallelised in a way similar to the all nearest smallest value problem. There is no source, and I have not been able to find any. The crucial difference between Graham and ANSV is that point p_{i + 2} in the convex hull depends on both p_{i + 1} and p_{i}. That introduces a dependency that cannot be resolved with the same technique (building a binary tree where the parent of two points is the minimum). [[Special:Contributions/145.137.143.111|145.137.143.111]] ([[User talk:145.137.143.111|talk]]) 08:35, 8 December 2023 (UTC)