Talk:Convex hull

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

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)

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)

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)

Too technical

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)

Sarcasm is unhelpful. Where did you run into trouble?  Kiefer.Wolfowitz 16:08, 11 June 2011 (UTC)

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)

Infinite dimensional?

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)

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)

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)

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)

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)

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)

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)

Copyright violation?

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)

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)

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)

Carathéodory's theorem

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)

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

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)

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 · log₂ 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)