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.

Example plot

  • $\begingroup$ You want an edge or set of edges? $\endgroup$ – Aryabhata Jun 4 '11 at 17:40
  • $\begingroup$ I think you have not clearly stated your problem. So there is given a finite set $A$ of points in the plane. You want a subset which is somehow lying on the bottom (with respect to $y$). Such a subset will consist of of $>2$ points, so how can it define "a line"? Maybe this "line" is in fact a polygonal arc - why should all this be "fundamentally different" from searching for the convex hull of $A$? $\endgroup$ – Christian Blatter Jun 4 '11 at 21:06
  • 4
    $\begingroup$ This is called the "lower convex hull" (do a Google search). Many convex hull algorithms separately compute it and the upper convex hull to create the convex hull. $\endgroup$ – whuber Jun 4 '11 at 21:52
  • $\begingroup$ @Cristian : I am after a polygonal arc here. $\endgroup$ – Zaid Jun 5 '11 at 5:17

It looks like you are looking for the lower [convex] hull. Some algorithms such as the Andrew's variant of Graham Scan actually compute this and compute the upper hull and then merge these two to obtain the convex hull. Andrew's algorithm can also be seen as a sweep algorithm, so if you want a quick implementation, you could just a vertical sweep algorithm (see the Wiki link for details).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.