![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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.
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)
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)
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.
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?
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)
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)
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:
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.
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)
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)
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:
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).
Cheers.— InternetArchiveBot ( Report bug) 18:47, 12 August 2017 (UTC)
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)
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)
![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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.
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)
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)
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.
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?
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)
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)
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:
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.
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)
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)
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:
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).
Cheers.— InternetArchiveBot ( Report bug) 18:47, 12 August 2017 (UTC)
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)
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)