Talk:Convex hull
From Wikipedia, the free encyclopedia
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)
- You are wrong. Sorry, I have no intentions to teach you math. get yourself a book in computational geometry. mikka (t)
- 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)
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)
