Given N lines on a Cartesian plane. How to find the bottommost intersection of lines efficiently?

Question

I have N distinct lines on a cartesian plane. Since slope-intercept form of a line is, y = mx + c, slope and y-intercept of these lines are given. I have to find the y coordinate of the bottommost intersection of any two lines.

I have implemented a O(N^2) solution in C++ which is the brute-force approach and is too slow for N = 10^5. Here is my code:

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> lines(n);

    for (int i = 0; i < n; ++i) {
        int slope, y_intercept;
        cin >> slope >> y_intercept;

        lines[i].first = slope;
        lines[i].second = y_intercept;
    }
    double min_y = 1e9;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (lines[i].first ==
                lines[j].first)   // since lines are distinct, two lines with same slope will never intersect
                continue;
            double x = (double) (lines[j].second - lines[i].second) / (lines[i].first - lines[j].first); //x-coordinate of intersection point
            double y = lines[i].first * x + lines[i].second; //y-coordinate of intersection point
            min_y = min(y, min_y);
        }
    }
    cout << min_y << endl;
}

How to solve this efficiently?

Answer 1

In case you are considering solving this by means of Linear Programming (LP), it could be done efficiently, since the solution which minimizes or maximizes the objective function always lies in the intersection of the constraint equations. I will show you how to model this problem as a maximization LP. Suppose you have N=2 first degree equations to consider:

y = 2x + 3
y = -4x + 7

then you will set up your simplex tableau like this:

 x0  x1  x2  x3   b
-2    1   1   0   3
 4    1   0   1   7

where row x0 represents the negation of the coefficient of "x" in the original first degree functions, x1 represents the coefficient of "y" which is generally +1, x2 and x3 represent the identity matrix of dimensions N by N (they are the slack variables), and b represents the value of the idepent term. In this case, the constraints are subject to <= operator.

Now, the objective function should be:

 x0  x1  x2  x3
 1    1   0   0

To solve this LP, you may use the "simplex" algorithm which is generally efficient.

Furthermore, the result will be an array representing the assigned values to each variable. In this scenario the solution is:

           x0               x1                x2               x3
 0.6666666667     4.3333333333               0.0              0.0

The pair (x0, x1) represents the point which you are looking for, where x0 is its x-coordinate and x1 is it's y-coordinate. There are other different results that you could get, for an example, there could exist no solution, you may find out more at plenty of books such as "Linear Programming and Extensions" by George Dantzig.

Keep in mind that the simplex algorithm only works for positive values of X0, x1, ..., xn. This means that before applying the simplex, you must make sure the optimum point which you are looking for is not outside of the feasible region.

EDIT 2: I believe making the problem feasible could be done easily in O(N) by shifting the original functions into a new position by means of adding a big factor to the independent terms of each function. Check my comment below. (EDIT 3: this implies it won't work for every possible scenario, though it's quite easy to implement. If you want an exact answer for any possible scenario, check the following explanation on how to convert the infeasible quadrants into the feasible back and forth)

EDIT 3: A better method to address this problem, one that is capable of precisely inferring the minimum point even if it is in the negative side of either x or y: converting to quadrant 1 all of the other 3.

Consider the following generic first degree function template:

f(x) = mx + k

Consider the following generic cartesian plane point template:

p = (p0, p1)

Converting a function and a point from y-negative quadrants to y-positive:

y_negative_to_y_positive( f(x) ) = -mx - k
y_negative_to_y_positive( p )    = (p0, -p1)

Converting a function and a point from x-negative quadrants to x-positive:

x_negative_to_x_positive( f(x) ) = -mx + k
x_negative_to_x_positive( p )    = (-p0, p1)

Summarizing:

  quadrant     sign of corresponding (x, y)                    converting f(x) or p to Q1
Quadrant 1                           (+, +)                               f(x)                            
Quadrant 2                           (-, +)               x_negative_to_x_positive( f(x) )
Quadrant 3                           (-, -)    y_negative_to_y_positive( x_negative_to_x_positive( f(x) ) )
Quadrant 4                           (+, -)               y_negative_to_y_positive( f(x) )

Now convert the functions from quadrants 2, 3 and 4 into quadrant 1. Run simplex 4 times, one based on the original quadrant 1 and the other 3 times based on the converted quadrants 2, 3 and 4. For the cases originating from a y-negative quadrant, you will need to model your simplex as a minimization instance, with negative slack variables, which will turn your constraints to the >= format. I will leave to you the details on how to model the same problem based on a minimization task. Once you have the results of each quadrant, you will have at hands at most 4 points (because you might find out, for example, that there is no point on a specific quadrant). Convert each of them back to their original quadrant, going back in an analogous manner as the original conversion.

Now you may freely compare the 4 points with each other and decide which one is the one you need.

EDIT 1:

1. Note that you may have the quantity N of first degree functions as huge as you wish.
2. Other methods for solving this problem could be better.
3. EDIT 3: Check out the complexity of simplex. In the average case scenario, it works efficiently.

Cheers!