Talk:Gift wrapping algorithm

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics ??? This article has not yet received a rating on the project's priority scale.

I think this article needs an explanation why it's supposedly O(NK). I don't see why that would be the case. It seems O(N²K) to me. -- Timwi 22:07, 9 Feb 2004 (UTC)

Answer: the outer loop runs K times (since it finds one point on the convex hull during each iteration) while the inner loop (which is not spelled out in the article) runs up to N-1 times. Hence O(K*N).

Where did you get N² from? `'mikka (t) 23:40, 21 July 2006 (UTC)Reply

The cited Introduction To Algorithms (a must have!) explains the performance. Wouter Lievens 22:59, 21 July 2006 (UTC)Reply

The citationd doesn't outline higher dimensional extensions, does anyone know about this 129.78.64.106 01:50, 1 February 2007 (UTC)Reply

What is the name of Mr/Mrs Jarvis? Wojciech mula (talk) 18:49, 8 May 2011 (UTC)Reply

"The algorithm may be easily modified to deal with collinearity, including the choice whether it should report only extreme points (vertices of the convex hull) or all points that lie on the convex hull."

This kind of language is unhelpful given a broad range of potential readers, especially given the technical nature of the content. Substantive remarks that clarify or outline the modifications suggested would fix this. 98.150.246.242 (talk) 23:56, 24 November 2013 (UTC)Reply

The C# implementation that is linked to from the article is not useful to anyone. It is ridiculously complicated by: being a bunch of 12 files; the only one file that is relevant to the algorithm is itself several times larger than is needed; it involves angles, division and trigonometric operations, all of these out of place (addition/subtraction and multiplication of coordinates is all that is needed). In addition, it is written in a language that requires a proprietary programming environment to compile and execute programs in.