WikiProject Mathematics	(Rated Start-class, Low-importance)
Mathematics portal 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. Mathematics rating: Start Class Low Importance  Field: Geometry

What does this mean?

coordinateList O, listOne, listTwo;

what does this mean?

Approximations

The article should mention finding an approximation of the convex hull, on-line / real-time algorithms, i.e. O(n^2) Graham scan modification, and Preparata's "An Optimal Real-Time Algorithm for Planar Convex Hulls", and dynamic convex hulls (maintaining the convex hull when points are being both added and deleted). —Preceding unsigned comment added by Blandwa (talk • contribs) 13:26, 23 July 2009 (UTC)

Animation

I want your opinion about this link

http://www.advancedmcode.org/fast-convex-hull-algorithm.html

I added it in the external link but it was removed. In my opinion it is not spam. It is a Convex Hull Algorithm (Open source), I was also planning to write some text about it. The link points to a video demostration (very instructive), isn't that good?

My impression is that it was removed without even see it.

Waiting for your opinion —Preceding unsigned comment added by Bracchesimo (talk • contribs) 15:07, 14 October 2009 (UTC)

I like the animation. I started to wonder if you could create a similar animation for one of the classical algorithms described on this page, e.g., the Graham scan? Perhaps a GIF animation would be a better (at least more compact) format? Then if you published it under the CC-BY-SA license, you could upload it to Wikimedia Commons, and we could use the animation directly on this page (and also on Graham scan). — Miym (talk) 15:37, 14 October 2009 (UTC)

Yes I can create a Graham scan GIF animation but there are thousands on the web. If you want, I will do it, but in my opinion that's an old story.

If you want I can also write something about my algorithm and how to make the computation of convex hull faster (tips and tricks). This article lacks some infos. Consider mine is a latin english so I thing I need your review.

I am asking your opinion becasue I experienced yet your "cleaning" attitude.

By the way, I am still convinced my link was useful.

Waiting for your feedback

Luigi —Preceding unsigned comment added by Bracchesimo (talk • contribs) 09:13, 15 October 2009 (UTC)

Melkman's algorithm

The description of Melkman's algorithm says: "If the resulting angle is concave, then the middle point is discarded and the next (along the polygon) vertex is added to the triple to be tested." Shouldn't the previous vertex be added there? The point is that if you remove a vertex, the vertex before it may now become concave. —Preceding unsigned comment added by 83.180.9.80 (talk) 11:12, 26 March 2010 (UTC)

I tried to write it down. But possibly someone can write a more readable text.

Lower bounds

Does anyone know why the following simple lower bound proof for the unordered convex hull does not work? Just as with reductiuon from sorting, we transform the number set into points on parabola and find the extreme vertices of their convex hull. If their count is less than N, then there were two equal input numbers, hence we have a reduction from the element uniqueness problem.

I was lazy to look into the text in Preparata-Shamos book carefully, but I was left with the impression that the tricky proof there is for a yet different problem: test whether N points are the vertices of their convex hull. Clearly, my simple reduction will not work for it.

Any ideas?

I thought about this reduction, and it seemed familiar. I looked at the lower bound argument given in O'Rourke's Computational Geometry in C, and it appears to be essentially the same as what you describe. The reduction given there goes all the way back to Shamos in 1978. Justin W Smith ^talk/_stalk 03:02, 29 April 2010 (UTC)

Oh, sorry... I think O'Rourke's lower bound might be the "reduction from sorting" you mentioned. Justin W Smith ^talk/_stalk 03:05, 29 April 2010 (UTC)

Duality

Something should be said about the dual problem where the given information is a set of linear constraints (half-spaces), and the goal is to find which constraints are irredundant.

The article currently says that "In higher dimensions, even if the vertices of a convex polytope are known, construction of its faces is a non-trivial task" -- I think that this, and the dual problem of finding the vertices when given the faces, could use some expansion. Joule36e5 (talk) 23:57, 15 September 2010 (UTC)

Sorting numbers is an O(N) operation

Integer and float numbers can be sorted with O(N) complexity using radix sort.

O(NlogN) is only required for comparison sorting. — Preceding unsigned comment added by 95.61.119.171 (talk) 15:52, 7 November 2011 (UTC)

If N is supposed to denote the number of values to be sorted, this is not true. Radix sort takes where w is the number of bits per value. Depending on how large w is, this may be larger or smaller than the time for comparison sorting. In any case, the issue is already discussed within the article; do you have any specific improvements to suggest? —David Eppstein (talk) 17:04, 7 November 2011 (UTC)

Ouellet's Convex Hull algorithm

Daniel Eppstein recently removed the modifications I have made to this related article. He pointed out that I violated 3 Wikipedia policies: No original research, Conflict of interest and Identifying reliable sources. I disagree for all the three. I already email him about it. I gave him my vision. But it seems that we have a different point of view. I think that removing my modifications will go against the benefits of Wikipedia users and I do not understand why Mr Eppstein still seems to prefer to remove them.

I copy here my latest email:

Mr. Eppstein,

As per the information on the web, you are a programmer with lots of experience that as a good knowledge in mathematic. You should know everything necessary to understand what I have wrote in Code Project and the ability to test it by yourself. I wonder if you have took the time to read the article at CodeProject before removing my words in Wikipedia?

About your 3 policies that your say I violated. That is exactly where I do not agree with you and where I would like to hear your interpretation of where I violate them:

• No original research: I can’t see what could be better than provided code to support an algorithm. How would you have done that to be more verifiable?
• Unreliable sources: Which unreliable source, I don’t understand of which sources you are talking about ?
• Self-promotion: Wikipedia: “… when advancing outside interests is more important to an editor than advancing the aims of Wikipedia, that editor stands in a conflict of interest”. I personally shared my code because it’s a brand new way of finding Convex Hull (which is far from every other known ways) and second it is very efficient, at the point where it is probably the fastest actual algorithm. I think that people has the right and interest to know that.

Regards, Eric Ouellet

I think that my proposed modifications was for the benefits of Wikipedia users and the advancement of the scientific community. Me, Eric Ouellet, author of the Ouellet Convex Hull, would appreciate to have other people opinions about it.