I have a 2D set and would like to determine from them the subset of points which, if joined together with lines, would result in an edge below which none of the points in the set exist.
This problem resembles the convex hull problem, but is fundamentally different in its definition.
One approach to determine these points might be to evaluate the cross-product of only
x_1 is on the 'hull',
x_2's 'hull'-ness is being evaluated and
x_3 is another point on the set (all other points in the set should yield positive cross products if
x_2 is indeed on the hull), with the additional constraint that
x_1 < x_2 in one dimension.
I realize that this algorithm is not entirely perfect; the plot below shows that some valid points would be missed as a result of the convex hull constraint. How else can I define this edge?
Hope the question is clear.