Editing Graham scan (section)

== Notes ==
The same basic idea works also if the input is sorted on x-coordinate instead of angle, and the hull is computed in two steps producing the upper and the lower parts of the hull respectively. This modification was devised by A. M. Andrew.<ref>{{cite journal|title=Another efficient algorithm for convex hulls in two dimensions|first=A. M.|last=Andrew|journal=Information Processing Letters|year=1979|volume=9|issue=5|pages=216–219|doi=10.1016/0020-0190(79)90072-3}}</ref>  It has the same basic properties as Graham's scan.<ref>{{Cite book
  | last1 = De Berg
  | first1 = Mark
  | last2 = Cheong
  | first2 = Otfried
  | last3 = Van Kreveld
  | first3 = Marc
  | last4 = Overmars
  | first4 = Mark
  | title = Computational Geometry Algorithms and Applications
  | url = https://archive.org/details/computationalgeo00berg_122
  | url-access = limited
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | year = 2008
  | pages = [https://archive.org/details/computationalgeo00berg_122/page/n12 2]–14
  | doi = 10.1007/978-3-540-77974-2
  | isbn = 978-3-540-77973-5 }}</ref>

Graham's original description involved sorting around an interior point of the [[convex hull]], rather than one of its vertices.<ref name=g72/> For the same choice of a pivot point for the sorting algorithm, connecting all of the other points in their sorted order around this point rather than performing the remaining steps of the Graham scan produces a [[star-shaped polygon]], a [[polygonalization]] of the input.<ref>{{cite conference
 | last1 = Arkin | first1 = Esther M.
 | last2 = Fekete | first2 = Sándor P.
 | last3 = Hurtado | first3 = Ferran
 | last4 = Mitchell | first4 = Joseph S. B.
 | last5 = Noy | first5 = Marc
 | last6 = Sacristán | first6 = Vera
 | last7 = Sethia | first7 = Saurabh
 | editor1-last = Aronov | editor1-first = Boris
 | editor2-last = Basu | editor2-first = Saugata
 | editor3-last = Pach | editor3-first = János
 | editor4-last = Sharir | editor4-first = Micha
 | contribution = On the reflexivity of point sets
 | doi = 10.1007/978-3-642-55566-4_6
 | mr = 2038472
 | pages = 139–156
 | publisher = Springer | location = Berlin
 | series = Algorithms and Combinatorics
 | title = Discrete and Computational Geometry: The Goodman-Pollack Festschrift
 | volume = 25
 | year = 2003| isbn = 978-3-642-62442-1
 }}</ref>

The stack technique used in Graham's scan is very similar to that for the [[all nearest smaller values]] problem, and parallel algorithms for all nearest smaller values may also be used (like Graham's scan) to compute convex hulls of sorted sequences of points efficiently.<ref>{{Cite journal|first1=Omer|last1=Berkman|first2=Baruch|last2=Schieber|author2-link=Baruch Schieber|first3=Uzi|last3=Vishkin|author3-link=Uzi Vishkin|title=Optimal double logarithmic parallel algorithms based on finding all nearest smaller values|journal=Journal of Algorithms|volume=14|pages=344–370|year=1993|issue=3|doi=10.1006/jagm.1993.1018|citeseerx=10.1.1.55.5669}}.</ref>