Talk:Convex hull algorithms

coordinateList O, listOne, listTwo;

what does this mean?

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]