Talk:Convex hull algorithms

Broken Link

The link to the three-dimensional convex hull library is broken: http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html. — Preceding unsigned comment added by Niccoloooo (talk • contribs) 14:20, 27 July 2016 (UTC)

And it's sill broken on 20 April 2017. Can I remove it? -Anonymous Wikipedian.

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

(outdated link, now domain to buy)

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 $O(N(1+{\frac {w}{\log N}}))$ 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.

Other convex hull algorithms

I feel that if there are less than a dozen known algorithms for efficiently computing something, Wikipedia should mention the name of each one.

I see that a well-meaning editor [1][2] apparently feels differently.

Rather than launch a revert war, could we discuss this? I suspect there is a simple misunderstanding somewhere. I think we agree that Wikipedia:Notability is an important guideline. Also, we seem to agree that a single reference for an algorithm is not enough to demonstrate the notability of that algorithm.

Many people seem to feel that a list of items should only include notable examples; that seems to be based on a misunderstanding of the WP:LISTN and WP:NLISTITEM guidelines. --DavidCary (talk) 17:32, 24 August 2015 (UTC)

That paper has only a single-digit number of citations in Google scholar. Given that there are about 5000 hits for the exact phrase "convex hull algorithm", that's not enough to convince me that it makes a big enough contribution to the subject to be worth including here. One could also cite evidence of inclusion in textbooks, etc., but with likely the same conclusions. —David Eppstein (talk) 17:39, 24 August 2015 (UTC)

According to wikipedia rules, the correctness of information is verified by references outside wikipedia. In our case the novelty and correctness of the algorithm, and claims of its superiority must be verified by a review independent of the authors. That's why we require secondary sources for citation. I've seen numerous convex hull algorithms (by the way, not half dozen; there are hundreds publications) and all of them claim be better than previous ones, and some of them being erroneous, and most of them forgotten. - üser:Altenmann >t 14:52, 25 August 2015 (UTC)

Re: "Many people seem to feel that a list of items should only include notable examples". WP:LISTN is about notability of topics to make a separate article, so it is inapplicable. The gist of this case is closer to WP:TRIVIA and WP:UNDUE. In our case, being nonnotable, i.e., not noted by others, the new algorithm lacks verification from peer math community, therefore it is not acceptable. - üser:Altenmann >t 15:18, 25 August 2015 (UTC)

Wikipedia:Stand-alone lists#Common selection criteria says: but List of Norwegian musicians would not be encyclopedically useful if it indiscriminately included every garage band mentioned in a local Norwegian newspaper. . It also says OK to Short, complete lists of every item that is verifiably a member of the group. , but: However, if a complete list would include hundreds or thousands of entries, then you should use the notability standard to provide focus to the list.. As I said, there are hundreds of convex hull publications, and we have to be selective. - üser:Altenmann >t 15:18, 25 August 2015 (UTC)

I agree that there are far too many papers and publications and textbooks that discuss convex hull algorithms to list each one in this article.

However, I hope you agree with me than an algorithm is not the same thing as a paper that describes it.

I hope you agree with me that when any editor states some fact in a Wikipedia article, that fact needs to be WP: verifiable, but the published work(s) we cite to help verify that fact does not itself need to be notable, merely WP: reliable.

most of them forgotten. I hope you agree with me that people reading an article about convex hull algorithms are often people who once knew something about the topic, and specifically *want* to read about things they have forgotten.

The WP:PRIMARY policy allows us to use primary sources as a citation for the fact that a certain convex hull algorithm exists. We do not require secondary sources for citation. I agree that secondary sources are great, and I think it would be awesome if secondary sources were used to cite every fact in this article, replacing every primary source.

I feel that if there are less than a dozen known algorithms for efficiently computing something, Wikipedia should mention the name of each one -- the fact that it exists -- even if the citation we use for that fact is not in the top-100 "best" convex hull publications.

I find it refreshing that David Eppstein and Altenmann have perfectly reasonable objections. I wish more people used such calm and reasoned statements. --DavidCary (talk) 17:14, 1 September 2015 (UTC)

• You wrote: "for efficiently computing something," Golden words. Now, how do we know that the algorithm in question computes anything at all? we have only author's words. There are lots of erroneous sci articles. Until it is reviewed by peers in secondary sources, its listing here is undue. WP:PRIMARY urges caution. We don't need tell the world that a certain algorithm exists, if we don't know it is not garbage. It was published 8 years ago. If during this time nobody commented on it, wikipedia is not in the business of unearthing unknown geniuses. - üser:Altenmann >t 15:27, 2 September 2015 (UTC)
• Now, I could consider listing it if it had a novel idea, even unverified. In our case the description says "Another output-sensitive algorithm with the same time bound as the Kirkpatrick–Seidel and Chan algorithms." Where is novelty worth mentioning in wikipedia? Now let us read the abstract: ""

  When the edges of a convex polygon are traversed along one direction, the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons, a new algorithm for computing the convex hull of a simple polygon is proposed

A true revelation, isn't it?

• First, the extreme points of the planar point set are found, and the subsets of point candidate for vertex of the convex hull between extreme points are obtained.

A rip-off of Akl-Toussaint heuristics. It well-known that AT heuristics is applicable as a pre-processing step to any CH algorithm. And moreover, it has other interesting advantages.

• the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull.

Yes, sure, a very smart move. Everybody does so after applying AT

• Compared with the algorithm having the same complexity, the new algorithm is much faster

Obviously the person who can write this has no idea about the peculiarities of big-Oh.

Conclusion: the article is waste of forest written by a person with apparent lack of knowledge of prior art trying to invent a better mousetrap based on a characteristic: "a trap in which the mouse is on the same side from all sides of the trap." - üser:Altenmann >t 15:27, 2 September 2015 (UTC)

• re:an algorithm is not the same thing as paper. Yes. We can readily verify that the paper is a valid publication, but we cannot verify that the algorithm is a valid procedure which does what it claims. And it is not the business of wikipedians to do so: we leave this for secondary sources. And it is not the business of wikipedia to list all published: wikipedia is not a directory. We don't list addresses of all Pizza Hut franchises, even though they are perfectly verifiable, profitable businesses, and some people may find such list useful. - üser:Altenmann >t 15:37, 2 September 2015 (UTC)

And yet Wikipedia does list all Walt Disney Parks and Resorts. It seems to me that the differences between our coverage of these businesses is in accordance with Wikipedia:Stand-alone lists#Common selection criteria: "Short, complete lists of every item that is verifiably a member of the group. ... However, if a complete list would include hundreds or thousands of entries, then you should use the notability standard to provide focus to the list." -- one business has relatively few locations, while the other business has hundreds or thousands of locations.

If I understand user:Altenmann correctly, one description of an algorithm does not have enough "novelty" to be mentioned in this Wikipedia article; it describes stuff that "Everybody does". To me, that implies that Altenmann thinks the described algorithm is not significantly different from some other, earlier convex hull algorithm. Assuming that is the case, I agree, but -- What is the name of that other, earlier convex hull algorithm? I want to mention that other, earlier algorithm in this article. Then perhaps people with apparent lack of knowledge of prior art will see this article and learn about this prior art algorithm, rather than reinventing the wheel all over again and trying to pass it off as a new invention. --DavidCary (talk) 05:22, 16 September 2015 (UTC)

You miss the major point: there are no secondary sources which write about this algorithm and evaluate it, unlike Disney Resorts (and therefore a more valid comparison would be List of Pizza Huts). Therefore it is undue to include it into wikipedia. And no, you did not understand me correctly: I think that the author lacks basic knowledge in the area, and my comments were simply an explanation of my opinion why experts disregard this algorithm. Wikipedia is not in the business of peer reviewing of nonnotable reinvented wheels, proofs of Fermat's Last Theorem and other semiscientific works published in obscure journals all over the world. - üser:Altenmann >t 14:56, 17 September 2015 (UTC)

Experts disregard the algorithm not only because it's published in an obscure place but also because it's so badly written that one cannot make heads or tails of it. —David Eppstein (talk) 16:05, 17 September 2015 (UTC)

Eric Ouellet writes about this algorithm and evaluates it. ( Eric Ouellet. "A Convex Hull Algorithm and its implementation in O(n log h)". ).

Are there really "numerous convex hull algorithms ... hundreds"? If so, please edit this article to mention that fact. I think I'm not the only person who read this article and got the (incorrect?) impression that there are less than a dozen "Known convex hull algorithms". --DavidCary (talk) 14:34, 21 October 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Convex hull algorithms. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20130626083150/http://michal.is/projects/convex-hull-gift-wrapping-method/ to http://michal.is/projects/convex-hull-gift-wrapping-method/

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 18:47, 12 August 2017 (UTC)

"eventually"

This edit introduced the word "eventually" into the following sentence in the lead:

The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and h, the number of points on the convex hull.

became

The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and, eventually, h, the number of points on the convex hull.

I cannot make sense of the meaning of the word in the latter sentence, and the edit summary here did not help. Nbro (talk · contribs), could you please write out in a few complete sentences what you think is wrong with the current version, and what change in meaning you are hoping for? Thanks, JBL (talk) 15:31, 19 April 2018 (UTC)

Would it be enough to change "and" to "or" in that sentence? --JBL (talk) 15:32, 19 April 2018 (UTC)

"or" would be incorrect. There is no algorithm that uses "h" in its complexity without also using "n". —David Eppstein (talk) 16:14, 19 April 2018 (UTC)

Ors can be inclusive; "n or h and n" sounds terrible, unfortunately. (I am just guessing that this is what Nbro was on about.) --JBL (talk) 17:44, 19 April 2018 (UTC)

How about "usually estimated in terms of n...and sometimes also in terms of h..."? —David Eppstein (talk) 18:02, 19 April 2018 (UTC)

That's very clean, I will implement it. --JBL (talk) 20:37, 19 April 2018 (UTC)

I am sorry. I thought the word "eventually" meant something different. I wanted to say something like "usually estimated in terms of n...and sometimes also in terms of h...".

Lower bound on computational complexity

I do not think the assumption is correct, that finding the convex hull can not be faster than sorting. The "proof" relies on a curve where each point is on the convex hull. Usually there are only a few points on the convex hull, which means of all points n only the points c (point on convex hull) require sorting. This results in an O(n) + O(c log c) lower bound (identification of convex hull point and sorting). Practically I measured the Gift Wrapping algorithm complete significantly faster than just the time required for sorting by x for the Graham Scan (up to around 5000 randomly distributed points -> less than 1% on convex hull). — Preceding unsigned comment added by GunterS (talk • contribs) 08:41, 21 August 2019 (UTC)

"Usually there are only a few points on the convex hull..." – Usually? Do you mean complexity in the worst case, or on the average (somehow)? Boris Tsirelson (talk) 08:57, 21 August 2019 (UTC)

QuickHull complexity

The description claims an expected complexity of O(n log n) for quickhull (like quicksort), but the main page on QuickHull does not have any such claim, the closest it has is a conjecture related to bit precision, not randomness. Mglisse (talk) 11:33, 28 October 2024 (UTC)

Quickhull is not randomized, so its expected time complexity makes no sense. There is no random distribution to take an expectation over. For some models of random input its average-case complexity (a different thing) is O(n). Its worst case complexity is O(n^2). As for the conjecture, see https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4989035 —David Eppstein (talk) 13:43, 28 October 2024 (UTC)

Exactly, so the claim "Just like the quicksort algorithm, it has the expected time complexity of O(n log n), but may degenerate to O(n2) in the worst case." should be modified or removed. Mglisse (talk) 08:31, 5 November 2024 (UTC)