Задано N линий на декартовой плоскости. Как найти самое нижнее пересечение линий?

Question

У меня есть N отчетливые линии на декартовой плоскости. Поскольку форма линии наклона-перехвата имеет вид y = mx + c, даются наклон и у-пересечение этих линий. Я должен найти координату y самого нижнего пересечения любых двух линий.

Я реализовал решение O(N^2) в C ++, которое является методом грубой силы и слишком медленное для N = 10^5. Вот мой код:

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;
}

Как это эффективно решить?

Answer 1

В случае, если вы рассматриваете решение этой проблемы с помощью линейного программирования (LP), это может быть сделано эффективно, поскольку решение, которое минимизирует или максимизирует целевую функцию, всегда лежит в пересечении уравнений ограничения. Я покажу вам, как смоделировать эту проблему как максимизирующий LP. Предположим, у вас есть N = 2 уравнения первой степени для рассмотрения:

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

, тогда вы создадите свою симплексную таблицу следующим образом:

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

где строка x0 представляет отрицание коэффициента «x» в исходных функциях первой степени, x1 представляет коэффициент «y», который обычно равен +1, x2 и x3 представляют единичную матрицу измерений N на N (они являются переменными слабины), а b представляет значение идеального срока. В этом случае ограничения подчиняются оператору <=. </p>

Теперь целевая функция должна быть:

 x0  x1  x2  x3
 1    1   0   0

. Чтобы решить этот LP, вы можете использовать «симплексный» алгоритм, который обычно эффективен.

Кроме того, результатом будет массив, представляющий назначенные значения для каждой переменной. В этом сценарии решение выглядит следующим образом:

           x0               x1                x2               x3
 0.6666666667     4.3333333333               0.0              0.0

Пара (x0, x1) представляет искомую точку, где x0 - ее x-координата, а x1 - ее y-координата. Есть и другие разные результаты, которые вы могли бы получить, например, не могло существовать никакого решения, вы можете узнать больше в большом количестве книг, таких как «Линейное программирование и расширения» Джорджа Данцига.

Имейте в виду что симплексный алгоритм работает только для положительных значений X0, x1, ..., xn. Это означает, что перед применением симплекса вы должны убедиться, что оптимальная точка, которую вы ищете, не находится за пределами допустимой области.

РЕДАКТИРОВАТЬ 2: Я считаю, что сделать задачу выполнимой можно было бы легко сделать в O (N), переместив исходные функции в новую позицию путем добавления большого фактора к независимым терминам каждой функции. Проверьте мой комментарий ниже. (РЕДАКТИРОВАТЬ 3: это подразумевает, что это не будет работать для каждого возможного сценария, хотя это довольно легко реализовать. Если вы хотите получить точный ответ для любого возможного сценария, посмотрите следующее объяснение о том, как преобразовать невозможные квадранты в выполнимую заднюю далее)

РЕДАКТИРОВАТЬ 3: лучший способ решения этой проблемы, способный точно вывести минимальную точку, даже если она находится в отрицательной части x или y: преобразование в квадрант 1 всех другое 3.

Рассмотрим следующий обобщенный c шаблон функции первой степени:

f(x) = mx + k

Рассмотрим следующий обобщенный c шаблон точки декартовой плоскости:

p = (p0, p1)

Преобразование функции и точки из y-отрицательных квадрантов в y-положительные:

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

Преобразование функции и точки из x-отрицательных квадрантов в x-положительные:

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

Подводя итог:

  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) )

Теперь преобразуйте функции из квадрантов 2, 3 и 4 в квадрант 1. Запустите симплекс 4 раза, один на основе o первоначальный квадрант 1, а остальные 3 раза на основе преобразованных квадрантов 2, 3 и 4. Для случаев, происходящих из y-отрицательного квадранта, вам нужно будет смоделировать симплекс как экземпляр минимизации с отрицательными слабыми переменными, которые превратятся в ваши ограничения в формате> =. Я оставлю вам подробности о том, как смоделировать ту же проблему на основе задачи минимизации. Как только вы получите результаты каждого квадранта, у вас будет на руках не более 4 баллов (потому что вы можете обнаружить, например, что нет никакого смысла в конкретном c квадранте). Преобразование каждого из них обратно в их первоначальный квадрант, аналогично исходному преобразованию.

Теперь вы можете свободно сравнивать 4 точки друг с другом и решать, какой из них вам нужен.

РЕДАКТИРОВАТЬ 1:

1. Обратите внимание, что вы можете иметь количество N первой степени функционирует так же огромно, как и вы sh.
2. Другие методы решения этой проблемы могли бы быть лучше.
3. РЕДАКТИРОВАТЬ 3: Проверьте сложность симплекс . В среднем случае это работает эффективно.

Приветствия!