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
, x_2
and x_3
, where 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.