Editing Graham scan (section)

==Numerical robustness==

[[Numerical robustness]] is an issue to deal with in algorithms that use finite-precision [[floating-point]] computer arithmetic. A 2004 paper analyzed a simple incremental strategy, which can be used, in particular, for an implementation of the Graham scan.<ref name= mkpsy/> The stated goal of the paper was not to specifically analyze the algorithm, but rather to provide a textbook example of what and how may fail due to floating-point computations in [[computational geometry]].<ref name= mkpsy>{{cite journal| doi=10.1016/j.comgeo.2007.06.003 | volume=40 | issue=1 | title=Classroom examples of robustness problems in geometric computations | year=2008 | journal=Computational Geometry | pages=61–78 | last1 = Kettner | first1 = Lutz | last2 = Mehlhorn | first2 = Kurt | last3 = Pion | first3 = Sylvain | last4 = Schirra | first4 = Stefan | last5 = Yap | first5 = Chee| url = http://hal.inria.fr/docs/00/34/43/10/PDF/RevisedClassroomExamples.pdf | doi-access = free }} (An earlier version was reported in 2004 at ESA'2004)</ref> Later D. Jiang and N. F. Stewart<ref>D. Jiang and N. F. Stewart, [http://www.iro.umontreal.ca/~stewart/JiangStewart11page.pdf Backward error analysis in computational geometry] {{Webarchive|url=https://web.archive.org/web/20170809013621/http://www.iro.umontreal.ca/~stewart/JiangStewart11page.pdf |date=2017-08-09 }}, Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series ''[[Lecture Notes in Computer Science]]'', pp 50–59</ref> elaborated on this and using the [[backward error analysis]] made two primary conclusions. The first is that the convex hull is a [[well-conditioned]] problem, and therefore one may expect algorithms which produce an answer within a reasonable error margin. Second, they demonstrate that a modification of Graham scan which they call Graham-Fortune (incorporating ideas of [[Steven Fortune]] for numeric stability<ref>{{cite book |last=Fortune |first=Steven |chapter=Stable maintenance of point set triangulations in two dimensions |title=30th Annual Symposium on Foundations of Computer Science |volume=30 |pages=494–499 |year=1989 |doi=10.1109/SFCS.1989.63524 |isbn=0-8186-1982-1 |chapter-url=http://www.computer.org/csdl/proceedings/focs/1989/1982/00/063524.pdf |archive-url=https://web.archive.org/web/20130728143644/http://www.computer.org/csdl/proceedings/focs/1989/1982/00/063524.pdf |archive-date=2013-07-28}}</ref>) does overcome the problems of finite precision and inexact data "to whatever extent it is possible to do so".