![]() | Convex hull has been listed as one of the
Mathematics good articles under the
good article criteria. If you can improve it further,
please do so. If it no longer meets these criteria, you can
reassess it. Review: April 11, 2020. ( Reviewed version). |
![]() | This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
|
The following paragraph was in the convex article, but since it's about convex hulls it would be better suited to this convex hull article. I'm leaving it on the Talk page for now, however, as I don't think it would add anything useful to this article either. -- Zundark 10:43, 16 Dec 2003 (UTC)
The Convex Hull article is inaccurate. Convex Hulls of 2D polygons are clearly Omega(n log n) by reduction to sorting: pick values x_i, compute convex hull of (x_i, x_i^2). Find point with smallest x, output the rest in order. Since a parabola is convex, the convex hull of the subset of the points will have all of them. For that to be the case, the output permutation will be such that points are output in order. If convex hulls were possible in Omega(n), then it would be possible to sort points in Omega(n). By a decision tree model, sorting points is Omega(n log n), and so is the convex hull.
A more up-to-date reference is: http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf (Lecture 4) 69.216.96.64 14:50, 15 September 2005 (UTC)
I don't think I understand the purpose of this parenthetical after the first sentence: "(Note that X may be the union of any set of objects made of points)." Even if there is a reason for this sentiment, we should try to find a better way to express it. Dchudz 16:53, 2 August 2006 (UTC)
I would like to thank anyone that has had a part in creating this article. The abundant use of terms and explanations that could only be understood by experts, with a complete disregard for the common man is excellent. I came here to try to understand convex hull approximations, as it could potentially be needed for an interactive project I'm currently working on. But it came as absolutely no surprise that, as most articles, it was explained in such a way where only individuals who already have somewhat of an idea about the subject could make good use of it. Fine work, experts. I shall crawl back to the cave of despair from which I came, miserable and hopeless as before. 90.229.248.197 ( talk) 06:14, 11 June 2011 (UTC)
A change today added a mention of convex hulls in infinite dimensional vector spaces. But, if one has a convex hull of infinitely many points in an infinite dimensional space, does one take all convex combinations for which the set of weights forms a series summing to one, or only those convex combinations with finite support? That is, is (1/2,1/4,1/8,...) a member of the convex hull of (1,0,0,...), (0,1,0,...), (0,0,1,...), ...? The definition of a convex hull as the minimal convex set containing a set of points, and the definition of a convex set as containing the line segment connecting any two of its points, leads to the finite support version. But, on the other hand, the definition of convex combination and of a convex hull as the set of all convex combinations seems to be stated in a way that would imply the other version. Perhaps this should be stated here more explicitly? — David Eppstein ( talk) 00:12, 24 May 2008 (UTC)
Forgive me (and correct me) if i'm not following appropriate protocol, however, i've noticed that the text in the "Applications" section, starting with the words "For example, consider the problem" and continuing through to "from one hull vertex to another", is word-for-word identical to a passage in the book, The Algorithm Design Manual by Steven Skiena (1998, Springer-Verlag New York), page 351 of the hardcover edition (section 8.6.2, "Convex Hull").
This text first appeared (with an additional sentence of quoted text from the book) in this revision, dating back to mid-2006. I've removed the content for the moment as a quick fix. Please advise if this is the incorrect course of action. Jmelesky ( talk) 23:42, 22 June 2008 (UTC)
Why do editors keep removing the reference to Carathéodory's theorem, without offering reasons or seeking consensus (at least since I've started watching this page)?
Of course, Carathéodory's theorem ( Farkas, Steinitz, etc.) exemplifies Stigler's " law of eponymy".
Kiefer.Wolfowitz ( talk) 14:57, 31 January 2010 (UTC)
I don't know the proper place to put this, so please feel free to delete / move / change this as necessary. I'm no expert on geometry, but it seems strange that I couldn't find an article on concave hulls, the associated challenges, or any algorithms or methods involved. A few searches turned up a publication , a query for general info , another query for info, and a java application for showcasing some algorithms. I don't know enough about geometry to know if I should create this page or if there is some other generalization where this type of information is located. If there is a page for this information, I wanted to request better linking to that data from this page, so that someone searching for concave hull information might find it easier than I have. If there is not, perhaps it should be created.
Crabpot8 ( talk) 15:10, 5 May 2011 (UTC)
There is a mention of Kallay's incremental algorithm, with no citation. I've looked for this algorithm for over an hour, and I can't find it. Is there a mistake or do I suck at finding things? — Preceding unsigned comment added by 67.80.148.73 ( talk) 10:27, 13 March 2012 (UTC)
I miss the definition of the lower and upper convex hull. The term is used for example in David Gross: Basic Structures of Function Field Arithmetic p. 39 def. 2.7. A definition I found in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.1152&rep=rep1&type=pdf But I know no texbook as a source. I would be very thankfull if somebody could add this. -- Flegmon ( talk) 11:36, 16 April 2012 (UTC)
It appears to me that the 4 given definitions of the convex hull are not all equivalent. Conditions 1, 2 and 4 are obviously equivalent, but condition 3 is distinct. Consider {(x,y):y>0} union {(0,0)} in the plane. This is convex and hence equals its convex hull. But it is not the intersection of a family of half-planes. GrantCairns ( talk) 12:25, 20 August 2012 (UTC)
Many thanks to David Eppstein to have corrected the article and the mistake of my previous post. D.Lazard ( talk) 09:16, 8 September 2012 (UTC)
The definition of complex hull given in the first sentence of the article implies (at least for those who understand the definition of convex set) that a convex hull is not a boundary, but a solid object.
Since "hulls" and "envelopes" are kinds of hollow containers in plain English, it is quite difficult to accept that in mathematics a convex "hull" or "envelope" is a solid (non-hollow) object, rather than an external surface or boundary. This is made even more difficult by the rubber-band example given in the introduction ("the convex hull may be visualized as the shape formed by a rubber band stretched around X"), which is not compatible with the above mentioned definition. According to that definition, the covex hull would be the space bounded by the rubber band, rather than "the shape formed by" it.
Are you sure that the reliable literature consistently defines a convex hull as a convex set (rather than its boundary)? If this is true, then the introduction should warn readers that in mathematics a hull is not a container... Otherwise, the introduction should say that according to some (reliable) authors the hull is just a boundary (similar to an elastic band), and according to some others it is a convex set.
In this context, it may be also useful for editors to notice that in English, whatever is inside a container is simply "contained in" it. However, the expressions "contained in" or "included in" are used in set theory to mean "member of", or "part of" the set. Therefore, if a container (such as a bottle or the hull of an airplane) is modeled as a set of particles, whatever is inside the container (a liquid or the passengers of an airplane) is not "contained in" it, as it is not a part of it. Paolo.dL ( talk) 15:04, 7 January 2013 (UTC)
So there can't be a pathological point set such that the union of simplices has a hole? — Tamfang ( talk) 03:31, 1 March 2013 (UTC)
The sentence "In fact, according to Carathéodory's theorem, if X is a subset of an N-dimensional vector space, convex combinations of at most N + 1 points are sufficient in the definition above" is misleading, as it appears to suggest that there exists set of $n+1$ vectors, such that convex combinations of them give the convex hull of the original set. Yet, this only gives a simplex and it is the union of many of these that give the complex hull of the original set, which implies that we need more than $n+1$ vectors. Rereading the sentence, perhaps misleading is too generous? 130.95.80.94 ( talk) 02:49, 24 October 2014 (UTC)
Some of these sound very interesting, but they are unsupported. Because this section is about applications, rather than finding citations that quote an author saying something like "convex hulls are useful for <blah>", it might be more helpful and interesting to the reader to link to, say, a paper that actually uses a convex hull for the listed application. Just an idea to consider. If I remember, I'll help add citations later. -- 166.20.224.10 ( talk) 19:49, 24 November 2014 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Bryanrutherford0 ( talk · contribs) 01:24, 9 April 2020 (UTC)
Thanks! Re the history: I wish I knew more but have been unable to find much. I did ask on the history of science stackexchange, not about Birkhoff and the name but about Newton [1] but didn't get any usable responses. — David Eppstein ( talk) 04:32, 9 April 2020 (UTC)
@ David Eppstein: [5] I don't see how it's OR to include the use in materials science when this is cited to book published by Cambridge University Press and Springer. A quick search would show that this is a well established topic in science [6], hence I'm wondering if you actually read the sources or instinctively lumped my edits in with the recent edits by another user. Pieceofmetalwork ( talk) 08:48, 22 June 2022 (UTC)
This article claims that the convex hull of a compact set is compact, but this appears to be false without assuming some extra conditions: https://math.stackexchange.com/questions/2017113/is-the-convex-hull-of-a-compact-set-compact 196.3.50.248 ( talk) 10:16, 22 December 2022 (UTC)
The terminology convex closure given in the introduction was added by an anonymous user almost 6 years ago, without any reference, and seems to have been unchallenged since.
However, I think that terminology is wrong and confusing, because a convex hull is not necessarily closed (in fact, as the article points out, the convex hull of an open set is always open) and thus can hardly be considered a "closure"... In fact, to me convex closure is a synonym of closed convex hull — which is a related but different notion.
Given the obvious nature of the problem and the way the term was added to the article, I was tempted to "be bold" and just remove it from the introduction. However, given that it has survived in the article for almost 6 years, I thought I'd start a discussion in case someone (@ David Eppstein? @ JBL? @ D.Lazard?) has a better suggestion; maybe a detailed remark along the lines of "in some communities convex closure is used for convex hull, but that this is incorrect in general because", etc?
Best, Malparti ( talk) 17:42, 8 January 2024 (UTC)
"convex closure"
in Google Books, the 6th result I get is Convex sets and their applications, Ky Fan (1959), where it's written: The reader is reminded to distinguish the two terms "convex hull" and "convex closure" (and there, convex closure does indeed mean the closure of the convex hull). So I don't think finding sources to backup the idea that one should be careful about the terminology should be a problem."convex closure"
on Google Books (I used Books instead of Scholar because I think textbooks are more relevant than research articles for a Wikipedia page). I looked at the first 4 pages (= 40 results), in the order in which Google Books listed them. I was able to access all these links from my institution, but not from my home; so some of the links below may not work for everybody.Meaning | Counts | Links |
---|---|---|
convex hull | 5 | 6, 16, 26, 27, 34 |
closed convex hull | 5 | 1, 5, 19, 25, 40 |
both | 1 | 33; also includes the example given by David Eppstein, since Weyl explicitsly considers closed sets. |
used only for functions | 6 | 2, 7, 10, 15, 21, 36 |
discarded (no access) | 0 | — |
discarded (unsure) | 3 | 3, 12, 14, 22, 24, 28, 32, 35, 38 |
discarded (too restricted) | 12 | 4 8, 11, 13, 17, 18, 20, 23, 29, 30, 31, 37, 39 |
![]() | Convex hull has been listed as one of the
Mathematics good articles under the
good article criteria. If you can improve it further,
please do so. If it no longer meets these criteria, you can
reassess it. Review: April 11, 2020. ( Reviewed version). |
![]() | This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
|
The following paragraph was in the convex article, but since it's about convex hulls it would be better suited to this convex hull article. I'm leaving it on the Talk page for now, however, as I don't think it would add anything useful to this article either. -- Zundark 10:43, 16 Dec 2003 (UTC)
The Convex Hull article is inaccurate. Convex Hulls of 2D polygons are clearly Omega(n log n) by reduction to sorting: pick values x_i, compute convex hull of (x_i, x_i^2). Find point with smallest x, output the rest in order. Since a parabola is convex, the convex hull of the subset of the points will have all of them. For that to be the case, the output permutation will be such that points are output in order. If convex hulls were possible in Omega(n), then it would be possible to sort points in Omega(n). By a decision tree model, sorting points is Omega(n log n), and so is the convex hull.
A more up-to-date reference is: http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf (Lecture 4) 69.216.96.64 14:50, 15 September 2005 (UTC)
I don't think I understand the purpose of this parenthetical after the first sentence: "(Note that X may be the union of any set of objects made of points)." Even if there is a reason for this sentiment, we should try to find a better way to express it. Dchudz 16:53, 2 August 2006 (UTC)
I would like to thank anyone that has had a part in creating this article. The abundant use of terms and explanations that could only be understood by experts, with a complete disregard for the common man is excellent. I came here to try to understand convex hull approximations, as it could potentially be needed for an interactive project I'm currently working on. But it came as absolutely no surprise that, as most articles, it was explained in such a way where only individuals who already have somewhat of an idea about the subject could make good use of it. Fine work, experts. I shall crawl back to the cave of despair from which I came, miserable and hopeless as before. 90.229.248.197 ( talk) 06:14, 11 June 2011 (UTC)
A change today added a mention of convex hulls in infinite dimensional vector spaces. But, if one has a convex hull of infinitely many points in an infinite dimensional space, does one take all convex combinations for which the set of weights forms a series summing to one, or only those convex combinations with finite support? That is, is (1/2,1/4,1/8,...) a member of the convex hull of (1,0,0,...), (0,1,0,...), (0,0,1,...), ...? The definition of a convex hull as the minimal convex set containing a set of points, and the definition of a convex set as containing the line segment connecting any two of its points, leads to the finite support version. But, on the other hand, the definition of convex combination and of a convex hull as the set of all convex combinations seems to be stated in a way that would imply the other version. Perhaps this should be stated here more explicitly? — David Eppstein ( talk) 00:12, 24 May 2008 (UTC)
Forgive me (and correct me) if i'm not following appropriate protocol, however, i've noticed that the text in the "Applications" section, starting with the words "For example, consider the problem" and continuing through to "from one hull vertex to another", is word-for-word identical to a passage in the book, The Algorithm Design Manual by Steven Skiena (1998, Springer-Verlag New York), page 351 of the hardcover edition (section 8.6.2, "Convex Hull").
This text first appeared (with an additional sentence of quoted text from the book) in this revision, dating back to mid-2006. I've removed the content for the moment as a quick fix. Please advise if this is the incorrect course of action. Jmelesky ( talk) 23:42, 22 June 2008 (UTC)
Why do editors keep removing the reference to Carathéodory's theorem, without offering reasons or seeking consensus (at least since I've started watching this page)?
Of course, Carathéodory's theorem ( Farkas, Steinitz, etc.) exemplifies Stigler's " law of eponymy".
Kiefer.Wolfowitz ( talk) 14:57, 31 January 2010 (UTC)
I don't know the proper place to put this, so please feel free to delete / move / change this as necessary. I'm no expert on geometry, but it seems strange that I couldn't find an article on concave hulls, the associated challenges, or any algorithms or methods involved. A few searches turned up a publication , a query for general info , another query for info, and a java application for showcasing some algorithms. I don't know enough about geometry to know if I should create this page or if there is some other generalization where this type of information is located. If there is a page for this information, I wanted to request better linking to that data from this page, so that someone searching for concave hull information might find it easier than I have. If there is not, perhaps it should be created.
Crabpot8 ( talk) 15:10, 5 May 2011 (UTC)
There is a mention of Kallay's incremental algorithm, with no citation. I've looked for this algorithm for over an hour, and I can't find it. Is there a mistake or do I suck at finding things? — Preceding unsigned comment added by 67.80.148.73 ( talk) 10:27, 13 March 2012 (UTC)
I miss the definition of the lower and upper convex hull. The term is used for example in David Gross: Basic Structures of Function Field Arithmetic p. 39 def. 2.7. A definition I found in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.1152&rep=rep1&type=pdf But I know no texbook as a source. I would be very thankfull if somebody could add this. -- Flegmon ( talk) 11:36, 16 April 2012 (UTC)
It appears to me that the 4 given definitions of the convex hull are not all equivalent. Conditions 1, 2 and 4 are obviously equivalent, but condition 3 is distinct. Consider {(x,y):y>0} union {(0,0)} in the plane. This is convex and hence equals its convex hull. But it is not the intersection of a family of half-planes. GrantCairns ( talk) 12:25, 20 August 2012 (UTC)
Many thanks to David Eppstein to have corrected the article and the mistake of my previous post. D.Lazard ( talk) 09:16, 8 September 2012 (UTC)
The definition of complex hull given in the first sentence of the article implies (at least for those who understand the definition of convex set) that a convex hull is not a boundary, but a solid object.
Since "hulls" and "envelopes" are kinds of hollow containers in plain English, it is quite difficult to accept that in mathematics a convex "hull" or "envelope" is a solid (non-hollow) object, rather than an external surface or boundary. This is made even more difficult by the rubber-band example given in the introduction ("the convex hull may be visualized as the shape formed by a rubber band stretched around X"), which is not compatible with the above mentioned definition. According to that definition, the covex hull would be the space bounded by the rubber band, rather than "the shape formed by" it.
Are you sure that the reliable literature consistently defines a convex hull as a convex set (rather than its boundary)? If this is true, then the introduction should warn readers that in mathematics a hull is not a container... Otherwise, the introduction should say that according to some (reliable) authors the hull is just a boundary (similar to an elastic band), and according to some others it is a convex set.
In this context, it may be also useful for editors to notice that in English, whatever is inside a container is simply "contained in" it. However, the expressions "contained in" or "included in" are used in set theory to mean "member of", or "part of" the set. Therefore, if a container (such as a bottle or the hull of an airplane) is modeled as a set of particles, whatever is inside the container (a liquid or the passengers of an airplane) is not "contained in" it, as it is not a part of it. Paolo.dL ( talk) 15:04, 7 January 2013 (UTC)
So there can't be a pathological point set such that the union of simplices has a hole? — Tamfang ( talk) 03:31, 1 March 2013 (UTC)
The sentence "In fact, according to Carathéodory's theorem, if X is a subset of an N-dimensional vector space, convex combinations of at most N + 1 points are sufficient in the definition above" is misleading, as it appears to suggest that there exists set of $n+1$ vectors, such that convex combinations of them give the convex hull of the original set. Yet, this only gives a simplex and it is the union of many of these that give the complex hull of the original set, which implies that we need more than $n+1$ vectors. Rereading the sentence, perhaps misleading is too generous? 130.95.80.94 ( talk) 02:49, 24 October 2014 (UTC)
Some of these sound very interesting, but they are unsupported. Because this section is about applications, rather than finding citations that quote an author saying something like "convex hulls are useful for <blah>", it might be more helpful and interesting to the reader to link to, say, a paper that actually uses a convex hull for the listed application. Just an idea to consider. If I remember, I'll help add citations later. -- 166.20.224.10 ( talk) 19:49, 24 November 2014 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Bryanrutherford0 ( talk · contribs) 01:24, 9 April 2020 (UTC)
Thanks! Re the history: I wish I knew more but have been unable to find much. I did ask on the history of science stackexchange, not about Birkhoff and the name but about Newton [1] but didn't get any usable responses. — David Eppstein ( talk) 04:32, 9 April 2020 (UTC)
@ David Eppstein: [5] I don't see how it's OR to include the use in materials science when this is cited to book published by Cambridge University Press and Springer. A quick search would show that this is a well established topic in science [6], hence I'm wondering if you actually read the sources or instinctively lumped my edits in with the recent edits by another user. Pieceofmetalwork ( talk) 08:48, 22 June 2022 (UTC)
This article claims that the convex hull of a compact set is compact, but this appears to be false without assuming some extra conditions: https://math.stackexchange.com/questions/2017113/is-the-convex-hull-of-a-compact-set-compact 196.3.50.248 ( talk) 10:16, 22 December 2022 (UTC)
The terminology convex closure given in the introduction was added by an anonymous user almost 6 years ago, without any reference, and seems to have been unchallenged since.
However, I think that terminology is wrong and confusing, because a convex hull is not necessarily closed (in fact, as the article points out, the convex hull of an open set is always open) and thus can hardly be considered a "closure"... In fact, to me convex closure is a synonym of closed convex hull — which is a related but different notion.
Given the obvious nature of the problem and the way the term was added to the article, I was tempted to "be bold" and just remove it from the introduction. However, given that it has survived in the article for almost 6 years, I thought I'd start a discussion in case someone (@ David Eppstein? @ JBL? @ D.Lazard?) has a better suggestion; maybe a detailed remark along the lines of "in some communities convex closure is used for convex hull, but that this is incorrect in general because", etc?
Best, Malparti ( talk) 17:42, 8 January 2024 (UTC)
"convex closure"
in Google Books, the 6th result I get is Convex sets and their applications, Ky Fan (1959), where it's written: The reader is reminded to distinguish the two terms "convex hull" and "convex closure" (and there, convex closure does indeed mean the closure of the convex hull). So I don't think finding sources to backup the idea that one should be careful about the terminology should be a problem."convex closure"
on Google Books (I used Books instead of Scholar because I think textbooks are more relevant than research articles for a Wikipedia page). I looked at the first 4 pages (= 40 results), in the order in which Google Books listed them. I was able to access all these links from my institution, but not from my home; so some of the links below may not work for everybody.Meaning | Counts | Links |
---|---|---|
convex hull | 5 | 6, 16, 26, 27, 34 |
closed convex hull | 5 | 1, 5, 19, 25, 40 |
both | 1 | 33; also includes the example given by David Eppstein, since Weyl explicitsly considers closed sets. |
used only for functions | 6 | 2, 7, 10, 15, 21, 36 |
discarded (no access) | 0 | — |
discarded (unsure) | 3 | 3, 12, 14, 22, 24, 28, 32, 35, 38 |
discarded (too restricted) | 12 | 4 8, 11, 13, 17, 18, 20, 23, 29, 30, 31, 37, 39 |