I have provided a picture as an example. We have two point sets, P and Q. P is to the left of this vertical line (named x = x0), and Q is to the right of it. The goal is to compute the line equations for both l1 and l2, as listed in the picture. My understanding is that this is a linear programming problem. The algorithm I'm looking for would run in O(n+m) time. I have only been able to find examples of O(n log n) time, and I'm not quite sure where else to look for O(n+m) time specifically.
Computing the line equations of two crossing tangents in a point set separated by a vertical line?
computational geometry;linear programming