Как найти сегмент, созданный путем соединения любой пары точек с максимальным наклоном?

Question

Дано n 2D точек.Рассмотрим все возможные сегменты, которые создаются путем объединения любой пары этих точек.Как найти сегмент с максимальным наклоном среди всех возможных сегментов в O (n * log (n))?

Можем ли мы отсортировать массив по координатам x и / или y?

1. Найдите y_i и y_j, такие, что y_i - y_j - максимальная разница, и найдите наклон (пусть будет delta_y);

2. найдите x_k и x_l таким, чтобы x_k - x_l было минимальным, и найдите наклон (пусть будет delta_x);

3. верните координаты x и ymax(delta_y, delta_x).

Это правильно?

Answer 1

Наклон - это отношение (delta_y)/(delta_x), где delta_y и delta_x измеряются между соответствующими точками.

Соотношение, вычисляемое вашим методом, составляет (y_i - y_j)/(x_k - x_l) для некоторых i, j, k и l, которые увеличивают y_i - y_j и минимизируют x_k - x_l. Но обратите внимание, что ни один из (x_k, y_i) или (x_l, y_j), скорее всего, не будет баллами из указанных n баллов. То есть ваш метод не измеряет delta_y и delta_x в соответствующих точках.

Чтобы прийти к методу, который работает, рассмотрим сортировку точек в порядке возрастания по x координате, что занимает O (n log n) времени. Затем за время O (n) проверьте, имеют ли какие-либо две точки одинаковую x координату. Если это так, существует бесконечный или неопределенный уклон. Еще рассмотрим уклоны между последовательными точками. Можно доказать, что самый крутой уклон между любой двумя из n точек происходит между последовательными точками, когда точки сортируются по возрастанию x. Следовательно, можно найти максимальный наклон за время O (n) после использования времени O (n log n) для сортировки точек.

Answer 2

Я думаю, что вы можете.Рассмотрим три последовательных пункта.Проведите линию от первой до третьей точки и посмотрите, находится ли средняя точка выше, ниже или ниже ее.Если средняя точка находится на прямой, все наклоны равны.Если средняя точка находится выше линии, то уклон от первой ко второй точке самый высокий.Если средняя точка находится ниже линии, то наклон от средней точки ко второй самый высокий.В любом случае вы можете найти наибольший уклон между двумя соседними точками.

Answer 3

Я не знаю, работает ли это или нет. Ответ открыт для предложений и правок.

Я буду использовать Разделяй и властвуй.

P - множество всех точек.

MAX_SLOPE(P)
   sort all the points in P according to ascending X coordinate and break ties using ascending Y coordinates.
   print(FIND_MAX_SLOPE(P))


FIND_MAX_SLOPE(P)
   if(P.length == 2)
      if(p1.x-p2.x != 0)
         return (p1.y-p2.y)/(p1.x-p2.x)
      else
         return 0
   else
      left_p = P[0..P.length/2]
      right_p = P[P.length/2..P.length]
      slope_left = FIND_MAX_SLOPE(left_p)
      slope_right = FIND_MAX_SLOPE(right_p)
      slope_across_border = FIND_MAX_SLOPE(left_p.last UNION right_p.first)
      return MAX(slope_left,slope_right,slope_across_border)