enter image description here

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.

  • $\begingroup$ Please don't re-post old questions - instead, we'd prefer that you edited the old question. Also, the comments there remain applicable: 1, 2. Can you describe your O(n log n) time algorithm in the question? $\endgroup$ – D.W. Mar 17 '17 at 16:18

Your Answer

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

Browse other questions tagged or ask your own question.