Jump to content

Talk:Convex hull

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Computational complexity of finding the convex hull over a finite set of points

[edit]

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)

One application of convex hulls is found in efficiency frontier analysis. Efficiency is assumed to be a monotonic function of each of finitely many real variables. Each one of finitely many data points is in exactly one hull, and is considered more efficient than all data points in hulls contained within its own hull. A particle whose velocity vector has a value of a for all coordinates representing maximized variables, and a value less than a for all minimized variables, will pass through the hulls in increasing order of efficiency.

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.

You better read more carefully. First, The O(n) is not for 2D polygons, but for 2D simple polygons. Second, how do you make a polygon from points (x_i, x_i^2)? mikka (t) 02:10, 20 July 2005 (UTC)[reply]
Connect (x_1, x_1^2) to (x_n, x_n^2), and you'll have a simple convex polygon. And for every non-simple polygon, there is a simple polygon with the same vertex set, so the simple/non-simple polygon distinction is pointless (because convex hull really only cares about the vertex set)
You are wrong. Sorry, I have no intentions to teach you math. get yourself a book in computational geometry. mikka (t)
So, while mikka is correct, the article could certainly use some explanation of how the algorithm for finding the convex hull of a simple polygon (or simple polyline) works. Simply stating that the problem has an O(n) solution isn't very interesting (though it does imply that constructing a simple polygon from a set of points is Omega(n log n)). A good web resource on some algorithms is at http://cgm.cs.mcgill.ca/~athens/cs601/ Cgray4 11:51, 2005 August 8 (UTC)

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

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

Too technical

[edit]

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

Sarcasm is unhelpful. Where did you run into trouble?  Kiefer.Wolfowitz 16:08, 11 June 2011 (UTC)[reply]
There was a misuse of "convex hull" for the boundary; this misuse may be an understandable convention in computational geometry, but its inclusion in the lead was confusing.
I moved the elastic band picture below, to the computational geometry section, because it focuses too much attention on the boundary of the convex hull.
I also removed an unreferenced self-labeled "intuitive" discussion, perhaps written under the influence of the ghosts of Fenchel, Busemann, and Alexandrov, but somewhat underdeveloped.
Readers should first read the articles on convex set and convex combination before reading this article.  Kiefer.Wolfowitz 16:36, 11 June 2011 (UTC)[reply]

Infinite dimensional?

[edit]

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

I see no bigger problem with a vector space of infinite dimension than with a vector space of finite dimension. In each case there is an infinite number of points, and the convex hull is the set of sums of convex combinations of finite number of points. The number of points in a convex combination is not tied in any way to the dimension of the space. Oleg Alexandrov (talk) 04:53, 24 May 2008 (UTC)[reply]
I agree that's the right definition. But our convex combination article doesn't clearly state that it's a combination of only finitely many; one could read it as allowing infinitely-supported combinations. —David Eppstein (talk) 06:45, 24 May 2008 (UTC)[reply]
Well, there is the number n there, which implies that the number of points is finite. I clarified that more there. Also, the possibility of an infinite amount of points is ruled out by the fact that it is impossible to talk about an infinite sum unless you have some kind of norm/topology which is not always the case in real vector spaces. Oleg Alexandrov (talk) 14:55, 24 May 2008 (UTC)[reply]
Much better. I still have a quibble: now convex combinations are defined only for finite sets of points, while here we say that the convex hull is the set of convex combinations of all of the points, so we can only define convex hulls of finitely many points. Two possible fixes: (1) in the convex combination article, define a convex combination of infinitely many points to be a weighted sum with finite support, or (2) here, define the convex hull as the set of convex combinations of finite subsets of the points. I think (1) would be preferable, but I'm not sure about it. —David Eppstein (talk) 15:34, 24 May 2008 (UTC)[reply]
David, I reverted your edit since I believe a definition using finite support convex combinations of an infinite number of points is not that usual (I think). I understand your point after I read this convex hull article. The recent changes to it made the definition unclear. The convex hull is not the convex combination of all points in the space, but rather the set of all possible convex combinations of finite tuples of points. I hope after my revert to the text this is more clear. Oleg Alexandrov (talk) 04:05, 25 May 2008 (UTC)[reply]
Convexity is a special case of sequential convexity, which is a special case of measure convexity; all of these inclusions are strict (and important). For sequential convexity, see Topology and Normed Spaces by G[raham]. J[ames]. O[scar] Jameson for sequential convexity. For measure convexity (c.f., Choquet theory), see Choquet order and simplices: with applications in probabilistic models by Gerhard Winkler (Springer Verlag, Lecture notes in mathematics ; 1145). Kiefer.Wolfowitz (talk) 17:32, 26 November 2009 (UTC)[reply]
[edit]

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

Thanks for spotting this! And it wasn't exactly a perfect formulation anyway, since the careless first sentence suggested that the diameter is a pair of points, not their distance. For lack of context it wasn't particularly clear either, and it may be best to drop this particular aspect altogether. --Hans Adler (talk) 00:13, 23 June 2008 (UTC)[reply]
I think it's an important aspect of the problem, and have added back a sentence that states it again without being a copyvio. Thanks for catching this. —David Eppstein (talk) 00:31, 23 June 2008 (UTC)[reply]

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


No article on concave hull (more specifically, on algorithms or methods for finding one)

[edit]

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

Yes this is an important and interesting problem. For example, computing the non-convex hull may be needed for pattern recognition (e.g. in OCR, or more generally when converting any rasterized image, or photography into a vectorized representation.
One majour problem is that the non-convex hull of a finite set of points is almost never unique. The first intuitive approach, which consists in minimizing the surface covered by the hull will not work and can bring an extremely large (combinatorial) number of solutions.
Generally the solutions try instead to minimize the surface covered by the bordering triangles, these triangles being defined by triplets of consecutive points on the hull. Another approach is to try to minimize the perimeter of the hull and this generally brings another solution. In all cases, you also need to define a maximum radius of search of candidate points to connect, because otherwise you will get the convex hull (which already has the smallest perimeter, but not the smallest area).
For the case of sets of infinitely many points, there's simply no solution, except if you define a maximum local radius of search, and if the density of nearby points within that radius is finite for every point of the infinite set; for example this case occurs:
  • if you try to define the "best" non-convex 2D hull of a fractal curve of the plane (with dimension more than 1 but still less than 2), such as the Koch flake.
  • in cartography, this case occurs when you try to define the non-convex boundary of the coast of Britanny or Norway: there's no limit to search candidate points, and at best you can only select points within a maximum search radius, so that all land will fall within that boundary, but you'll necessarily include parts of the sea. IF your search radius goes very low, the total perimeter of the non-convex hull may grow indefinitely (that's why it's simply impossible to reliably define the length of coasts of Britanny or Norway).
Searching such non-convex hull over a finite set of points is a np-complete problem (with combinatorial complexity). On the opposite, finding the convex hull has a MUCH lower complexity in O(n²), using an intuitive approach, where n is the number of points in the set, but in most cases an efficient algorithm can reduce this complexity to O(n · log2 n), provided that n is not too large, because space may be limited (for example not all points can fit in memory, they must be splitted into subsets that have to be paged out, with a huge time cost; in general the solution is to subdivide the set using tiled squares, and this solution is used in cartographic applications, such as OpenStreetMap, Bing Maps, Google Maps/Google Earth).
verdy_p (talk) 10:07, 27 July 2011 (UTC)[reply]

Kallay?

[edit]

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

Try Gil Kalai, and fix the typo if my guess is correct, please!  Kiefer.Wolfowitz 11:01, 13 March 2012 (UTC)[reply]

lower, upper convex hull

[edit]

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

Oh and it ist used in Newton_polygon --Flegmon (talk) 12:41, 16 April 2012 (UTC)[reply]
Do you know of an encyclopedia article that discusses such "convex hulls"? Are they hull operators, convexity systems, antimatroids?  Kiefer.Wolfowitz 16:21, 16 April 2012 (UTC)[reply]
I don't know how you want to abstract them, but they're very standard in computational geometry. I'll see if I can find a source in the computational geometry texts I have. —David Eppstein (talk) 16:48, 16 April 2012 (UTC)[reply]

Equivalence of definitions

[edit]

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

This comment looks right to me. What's the correct statement? Closed convex sets are the intersections of their halfspaces? Open? Something else? This characterization is obviously right and important in a large number of cases; what's the defining feature of those cases? --JBL (talk) 12:37, 7 September 2012 (UTC)[reply]
It seems that the editors of this article had in mind the convex hull of finite sets. I think that the correct assertions are the following ones:
  • The convex hull of a closed compact set (in particular of a finite set) is closed.
  • The convex hull of a closed compact is the intersection of the closed half hyperplanes containing it.
In any case, the given definition in term of intersection of half hyperplanes is meaningless without indicating it the half hyperplanes are open or closed. D.Lazard (talk) 13:32, 7 September 2012 (UTC)[reply]
I agree, this was wrong. I've refactored that part of the article to take this discussion into account. —David Eppstein (talk) 15:24, 7 September 2012 (UTC)[reply]

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

"Hull" as a container

[edit]

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

The word "hull" in mathematics can be used with very abstract meanings — see e.g. injective hull. —David Eppstein (talk) 15:37, 7 January 2013 (UTC)[reply]

simplices

[edit]
  • The union of all simplices with vertices in X.

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

Keep reading. In the paragraph that follows you'll find a link to Carathéodory's_theorem_(convex_hull). --JBL (talk) 04:08, 1 March 2013 (UTC)[reply]
Which seems obvious enough that I now wonder what prompted my question. —Tamfang (talk) 07:28, 10 February 2024 (UTC)[reply]

Definition ambiguity

[edit]

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

No citations in the Applications section

[edit]

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

I've added a specific application for home range with citation. —Mrwojo (talk) 23:07, 7 March 2015 (UTC)[reply]

GA Review

[edit]
This review is transcluded from Talk:Convex hull/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Bryanrutherford0 (talk · contribs) 01:24, 9 April 2020 (UTC)[reply]

GA review (see here for what the criteria are, and here for what they are not)
  1. It is reasonably well written.
    a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists):
    The prose standard is good. The article complies with the indicated portions of MoS, with a possible minor exception in the lead: MoS suggests that the lead section of an article this long should contain "two or three paragraphs", where this article currently has four. It's a guideline, so I won't hold back the nomination over it, but it's something to consider.
    Now three paragraphs, with more or less the same material. —David Eppstein (talk) 23:46, 9 April 2020 (UTC)[reply]
  2. It is factually accurate and verifiable.
    a (reference section): b (citations to reliable sources): c (OR): d (copyvio and plagiarism):
    The article contains many citations to reputable published sources. I see no signs of plagiarism from online sources, though one random site seems to have copied text from here. Spot-checking through the sources, it looks to me as though the Artin citation should link to page 37 of the text rather than page 3, and the de Berg et al. should link to page 3 rather than page 2. Is there some convention about linking the beginning of the section rather than the cited text that I'm not aware of? For verifiability's sake it seems more helpful to have the GBooks links point to the pages that are being cited.
    I'm pretty sure the Artin link was just a copy-and-paste error (not including the final character of the url); I fixed it. For the 4 Marks book, we are citing too many different pages to choose a single one for the link in the main reference, so I just removed the link. —David Eppstein (talk) 03:50, 11 April 2020 (UTC)[reply]
  3. It is broad in its coverage.
    a (major aspects): b (focused):
    The article maintains a suitable focus on its topic, and it generally achieves broad coverage, with a small exception for the concept's history. Is it known who coined this term or first began using it in its modern sense? The article mentions an early use but doesn't assert whether that is in fact the first. Is it known how or why this term came to be the standard one, rather than e.g. the other used earlier that is mentioned? The history section feels thin relative to the rest of the document, and I wish it told me more.
  4. It follows the neutral point of view policy.
    Fair representation without bias:
    The article maintains a suitably neutral tone and stance toward the topic, not e.g. exaggerating its significance.
  5. It is stable.
    No edit wars, etc.:
  6. It is illustrated by images and other media, where possible and appropriate.
    a (images are tagged and non-free content have fair use rationales): b (appropriate use with suitable captions):
    The images used in the article have suitable tagged licenses, and they are relevant and helpful to explaining the topic. I feel that File:3D Convex Hull.tiff would be better placed in "Special cases/Finite point sets", but there's already a good 2-D illustration there, and I don't think there's room for both; it's probably still helpful where it is.
  7. Overall:
    Pass/Fail:
    Excellent work! -Bryan Rutherford (talk) 13:06, 11 April 2020 (UTC)[reply]

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

The history intrigued me, too. I managed to dig up a couple articles by L. L. Dines (1936, 1938) who noted the use in German of "konvexe Hülle" and complained that "hull" should properly mean the outside surface rather than the whole body. I can find "konvexe Hülle" in this doctoral thesis from 1930, for example, though I rather doubt the database coverage for German-language papers from that era is very comprehensive. XOR'easter (talk) 23:15, 9 April 2020 (UTC)[reply]
Oh, hey, thanks, XOR! Haha I love what a collaborative effort WP is! Great work, David; I should have time to check through the sources tomorrow. -Bryan Rutherford (talk) 00:08, 10 April 2020 (UTC)[reply]
The German phrase is a good suggestion; thanks! I found, from 1922, Rademacher's review of König's "Über konvexe Körper" [2] and Fejer's "Über die Lage der Nullstellen von Polynomen, die aus Minimumforderungen gewisser Art entspringen" [3]. Curiously, König himself (also 1922, [4]) doesn't appear to call it a convex hull, but merely the smallest convex body (containing a given set). I'm a bit worried this is all verging too close to WP:OR, though. —David Eppstein (talk) 04:32, 10 April 2020 (UTC)[reply]
Yes, there is a hazard of WP:OR in pursuing this. I believe that what the current version says is acceptable in this regard, since it does not synthesize the data points to argue for a conclusion (e.g., claiming that these early examples are definitively the earliest on record). To me, it seems acceptable. We could possibly add Dines' claim that by 1938, the term convex hull was "firmly intrenched in the mathematical vocabulary". XOR'easter (talk) 18:58, 10 April 2020 (UTC)[reply]
Added. That part of the Dines source actually is about the terminology and not just an example of use of the terminology. —David Eppstein (talk) 23:13, 10 April 2020 (UTC)[reply]
That is excellent work, and I'm now totally satisfied on that front. Thank you, both! One tiny concern about some of the links to source texts, and we'll be there. -Bryan Rutherford (talk) 01:22, 11 April 2020 (UTC)[reply]
And, that'll do it! This article now meets the GA standard and is promoted. Thank you for your service! -Bryan Rutherford (talk) 13:06, 11 April 2020 (UTC)[reply]

In materials science

[edit]

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

Convex hull of a compact set

[edit]

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

This article is primarily about convex hulls in finite dimensional Euclidean spaces. In more general kinds of spaces like the one of that example, more general kinds of things can happen. —David Eppstein (talk) 07:50, 23 December 2022 (UTC)[reply]

Convex closure

[edit]

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

Google Scholar easily finds good sources for this term, such as by Hermann Weyl: [7]. So it is in use. As for whether it is "correct": closure is used in mathematics in lots of senses that do not mean topological closure (see for instance the closure operations of a matroid, or algebraic closure). We cannot write in our article that this terminology is somehow incorrect without reliable sources that make the same statement. —David Eppstein (talk) 18:12, 8 January 2024 (UTC)[reply]
(ec) Thanks for the ping. To address something that is not your main point: the convex hull is closed with respect to a certain operation (namely, taking points on the segment connecting two points in the set), just as the algebraic closure of a field is closed with respect to a certain operation (taking roots of polynomials with coefficients in the field) and the topological closure is closed with respect to a certain operation (taking limit points of sequences of points in the set). The algebraic closure of the rational numbers is not a closed set in the sense of topology (as a subset of the reals or complexes), and that is definitionally fine (it just requires authors to be a bit careful sometimes). So I don't think there's any issue of correctness here. --JBL (talk) 18:39, 8 January 2024 (UTC)[reply]
@David Eppstein @JBL thanks for the prompt reply.
I agree that "closure" can refer to other types of closures than topological ones. So incorrect wasn't the right word, misleading would have been better suited.
More to the point: my main concern is that, as I mentioned, convex closure can have the meaning of closed convex closure — a fairly common notion. And I suspect that most occurrences of convex closure actually refer to the closed convex closure, not to the convex hull; I'll do a quick literature search tomorrow to see if that claim actually holds.
Regarding David Eppstein's comment that we would need to base ourself on a reliable source if we want to discuss the whether the term convex closure is misleading: just by typing "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.
Best, Malparti (talk) 22:47, 8 January 2024 (UTC)[reply]
@David Eppstein @JBL Here are the results of my little experiment:
I searched for "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.
For each of these results, I determined whether convex closure referred to the convex hull, to the close convex hull, or to both (meaning that the authors are working in a setting where the convex hull is always closed). I made a special category for cases where convex closure was used exclusively to refer to the convex closure of a function (i.e. the closed convex hull of its epigraph), but those results should actually be counted in the category closed convex hull (the reason why I listed them separately is that it is a bit trickier for someone not familiar with the terminology to see what's going on). I discarded results for which I wasn't immediately sure what was going on, or where no definition was given; and, in a separate category, results or that seemed to be talking about something extremely specific (boolean vectors, networks, etc) that is likely not relevant for this Wikipedia article.
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
Here are a few comments on these limited data:
  • Some people do indeed use convex closure as a synonym of convex hull. Since, as pointed out above, the "convex-hull" operator is a closure operator, this makes sense.
  • However, most of the occurrences of that term refer to something different. Usually, that would be either:
    • the closed convex hull;
    • the closed convex hull of the epigraph of a function (in that case, a distinction is usually made between the convex closure and the convex hull [which is just the convex hull of the epigraph]).
    • a related notion with a more restrictive definition (usually in a specific context: discrete mathematics, computer science, logic...)
  • At least one very influential mathematician (Ky Fan) felt the need to point out that one should not confuse convex hull and convex closure.
  • The example of use by Hermann Weyl given above cannot really be used to support the use of convex closure as a synonym for convex hull rather than closed convex hull, since only closed sets are considered and so the convex hull and the closed convex hull coincide.
Having that in mind, I do not think that listing convex closure as a synonym of convex hull in the introduction without some additional explanation is a great idea. Not sure what is the best way to solve the problem, though. Here is a suggestion:
  1. Remove convex closure from the introduction
  2. In the section Closure operator, add something saying that the fact that the convex-hull operator is a closure operator leads some authors to refer to the convex hull has the convex closure; but that it should not be confused with the closed convex hull, which is can also be called convex closure (a reference to Ky Fan can be given here).
  3. In the section Closed and open hulls, mention that the closed open hull is sometimes simply called the convex closure. Ky Fan could be used again as a reference, but 1 is perhaps a bit nicer, as it's better typeset and has some pictures, etc.
Unless someone disagrees, I can take care of implementing those changes later this week.
Best, Malparti (talk) 16:13, 9 January 2024 (UTC)[reply]
Personally it seems to me that the natural thing to do in the lead would be to put a footnote (using template:efn) following the words "convex closure" observing that this phrase is also used for another operation, together with relevant citations, rather than removing a valid alternate term. Since the closed convex hull is almost certainly never going to have its own article, I agree that including the information about that operation in this article is very sensible. --JBL (talk) 19:26, 9 January 2024 (UTC)[reply]
@JBL The footnote in the lead works for me too. I'll let a bit of time pass to give other people a chance to chime in. Thanks for your input. Cheers, Malparti (talk) 22:24, 9 January 2024 (UTC)[reply]